Proofs: Spectral Bloom filter

The error probability of a spectral Bloom filter full

This proof shows: complexity.

Model. Assume ideal hashing: the values $h_i(y)$ for all $i \le k$ and all keys $y$ are independent and uniform on $\{0, \ldots, m - 1\}$. Fix the sequence of operations, so that the multiset $f$ does not depend on the hash values; neither rule reads a hash value to decide which key to update. Fix a key $x$, let $Y$ be the set of keys $y \ne x$ with $f_y > 0$, $n = |Y|$, and $B = \bigcup_{y \in Y} H(y)$.

Theorem 1. Under either rule, $\Pr[\hat f_x \ne f_x] \le \mathbb{E}[(|B|/m)^k]$. In particular it is at most $\big(1 - (1 - 1/m)^{kn}\big)^k$ up to the gap between the exact and the classical Bloom filter formulas, and it does not depend on the counts.

Proof. By Theorems 1 and 2 of the correctness proof, $f_x \le \hat f_x^{\mathrm{MI}} \le \hat f_x^{\mathrm{MS}}$, and $\hat f_x^{\mathrm{MS}} \ne f_x$ only if every $p \in H(x)$ lies in $B$. So for both rules the error implies $H(x) \subseteq B$. The set $B$ is a function of the hash values of the keys in $Y$, which are independent of $h_1(x), \ldots, h_k(x)$. Given $B$, each $h_i(x)$ lies in $B$ with probability $|B|/m$, independently, so

This is exactly the probability that a Bloom filter with the same $m$ and $k$, built from the $n$ keys of $Y$, accepts $x$, its false positive rate. Its classical estimate is $(1 - (1 - 1/m)^{kn})^k \approx (1 - e^{-kn/m})^k$. $\square$

Theorem 2 (time and space). Each operation evaluates $k$ hash functions and reads or writes at most $k$ counters, so it takes $\Theta(k)$ time on the word RAM when a counter fits in a word. The array takes $m$ counters. $\blacksquare$

A spectral Bloom filter never underestimates full

This proof shows: correctness, invariant, termination.

Fix the hash functions and a sequence of operations. Write $f$ for the multiset after the first $t$ operations, $C$ for the counters of minimum selection and $D$ for the counters of minimal increase on the same sequence of inserts. Each operation loops over at most $k$ positions, so it ends.

Lemma 1 (invariant (M)). Under minimum selection, after each operation $C[p] = \sum_{y : p \in H(y)} f_y$ for each $p$, provided every DELETE$(x, w)$ has $f_x \ge w$ before it.

Proof. At the start both sides are 0. INSERT$(x, w)$ adds $w$ to $f_x$, which adds $w$ to the right side exactly for the $p \in H(x)$, and line L3 adds $w$ to exactly these counters, once each, since $H(x)$ is a set. DELETE$(x, w)$ is the same with $-w$. $\square$

Theorem 1 (minimum selection). For each $x$, $\hat f_x = f_x + \min_{p \in H(x)} \sum_{y \ne x,\, p \in H(y)} f_y$. So $\hat f_x \ge f_x$, with equality exactly when some $p \in H(x)$ lies in $H(y)$ for no $y \ne x$ with $f_y > 0$.

Proof. By Lemma 1, for $p \in H(x)$ the counter is $C[p] = f_x + \sum_{y \ne x,\, p \in H(y)} f_y$, and line L7 takes the minimum over $p \in H(x)$. The sums have nonnegative terms, so the minimum is 0 exactly when one of them has no positive term. $\square$

Theorem 2 (minimal increase). If all operations are inserts and minimal increase is used, then after each insert, for each key $y$ and each $p \in H(y)$,

Hence $f_x \le \hat f_x^{\mathrm{MI}} \le \hat f_x^{\mathrm{MS}}$ for each $x$.

Proof. By induction over the inserts. At the start all values are 0. Consider INSERT$(x, w)$, and let $f'$, $C'$ and $D'$ be the values after it.

Lower bound. Let $v = \min_{p \in H(x)} D[p]$, the value of line L4. By the induction hypothesis $v \ge f_x$. Line L5 sets $D'[p] = \max(D[p], v + w) \ge f_x + w = f'_x$ for each $p \in H(x)$. For $y \ne x$, $f'_y = f_y$ and no counter decreases, so $D'[p] \ge D[p] \ge f_y$ for $p \in H(y)$.

Upper bound. For $p \notin H(x)$ nothing changes. For $p \in H(x)$, line L3 gives $C'[p] = C[p] + w$. If $D'[p] = D[p]$, then $D'[p] \le C[p] \le C'[p]$. Otherwise $D'[p] = v + w \le D[p] + w \le C[p] + w = C'[p]$, since $v \le D[p]$ for each $p \in H(x)$.

The estimates are minima over the same set $H(x)$ of values that satisfy the bounds pointwise, which gives the last claim. $\blacksquare$