Brief Introduction

Invertible Bloom Lookup Table (abbr. IBLT)

a fancy hash-table stores key-value pair $(x,y)$

space budget: $t$

Guarantee

It “works” when the number of key-value pairs, $n$ , in table has $n\le t$ .

“temporarily” stops working if $n\gt t$ .

starts working again if $n$ drops below $t$ .

(x,y) is key-value pair.

insert(x,y), delete(x,y), get(x), listentries.

Start with table with $k\ge3$ rows, $m=2\times t$ columns.

In each row, we have a hash function $h_1,\cdots,h_k$ .

$h_i$ is universal.

Each of the entry, called cell, stores values:

for $i=1$ $i = 1$ to $k$ $k$
- $c=A[i][h_i(x)]$
- $c.count++$
- $c.key\_sum+= x$
- $c.value\_sum+=y$

“undo” insert operation

We must know the pair is there before deletion.

for $i=1$ $i = 1$ to $k$ $k$
- $c=A[i][h_i(x)]$
- $c.count--$
- $c.key\_sum-= x$
- $c.value\_sum-=y$

slightly different from min sketch count

If $n\le t$ , then get(x) succeeds with probability $\ge1-2^{-k}$ .

Assume $k\gt1$ , $n$ pairs: $(x_i,y_i)$ is stored in IBLT, $n\le t$ .

For get(x)

If $x$ is in IBLT
1. 当 $x$ 在 IBLT 的这一行里面，但是 get 函数发现对应的哈希值指向的位置都发生了碰撞的概率。
2. 明明 $x$ 不在 IBLT 中，但是 get 函数发现对应的哈希值指向的位置中存在一个值，即 count=1 但 value 不是 $x$ 对应的。
Define fail-event $E_i:\{h(x)=h(x_i)\}$ ,

\Pr[get(x)\text{ fails}]=\Pr[\bigcup_{x_i\neq x}E_i]\le\sum_{x_i\neq x}\Pr[E_i]\\ \le\sum_{x_i\neq x}\frac{1}{m}=\frac{n-1}{m}\le\frac{t-1}{m}=\frac{t-1}{2t}\le\frac{1}{2}

If $x$ is not in IBLT.
明明 $x$ 不在 IBLT 的这一行里面，但是 get 函数得出该键对应的哈希值指向的位置在 IBLT 这一行中产生碰撞的概率。
Define fail-event $E_{ij}=\{h(x)=h(x_i)=h(x_j)\}$
$\Pr[\bigcup_{i\neq j}E_{ij}]\le\sum_{i\lt j}\Pr[E_{ij}]=\sum_{i\lt j}\frac{1}{m^2}=C_n^2\frac{1}{m^2}\\ =\frac{n(n-1)}{2m^2}\le\frac{t^2}{2m^2}\le\frac{t^2}{8t^2}=\frac{1}{8}$

If we choose $k=\log_2t+\log_2\frac{1}{\delta}$ , the probability of failure is at most $\delta$ .

another set of universal hash function $g_1,\cdots,g_k:U\rarr[R]$

while query, check whether $c.hash\_sum==g(c.key\_sum)$