Proofs: Stable Bloom filter

The stable fraction of zero cells full

This proof shows: complexity.

Model. At each step $t$, the set $H(x_t)$ is a uniform random $K$-subset of the $m$ cells and $V_t$ is a uniform random $P$-subset, and all these sets are independent. This holds under ideal hashing for a stream of distinct elements. Assume $1 \le K < m$ and $P \ge 1$.

Theorem 1. For each cell $j$,

Proof. Fix $j$. At each step $s$, let $A_s$ be the event $j \in H(x_s)$, a set, and $B_s$ the event $j \in V_s$ and $j \notin H(x_s)$, a pure decrement. Then $\Pr[A_s] = a = K/m$ and, by the independence of $H(x_s)$ and $V_s$, $\Pr[B_s] = b = (P/m)(1 - K/m)$. Steps are independent.

By the invariant (D) of the correctness proof, $C_t[j] = 0$ exactly when either no step $s \le t$ is a set, or the last set $\tau$ is followed by at least Max pure decrements in the steps $\tau + 1, \ldots, t$ (a step that is both a set and a decrement counts as a set, since line L4 runs after line L3).

Look at the steps $t, t - 1, \ldots, 1$ in this order, and keep only the relevant steps, those that are a set or a pure decrement. Since the steps are independent and identically distributed, each relevant step is, independently of the others, a pure decrement with probability

and a set otherwise. The cell is 0 at time $t$ if and only if the first Max relevant steps in this backward order are all pure decrements, or there are fewer than Max relevant steps and none is a set.

Let $R_t$ be the number of relevant steps among $1, \ldots, t$. Given $R_t = \rho \ge \mathrm{Max}$, the first event has probability exactly $q^{\mathrm{Max}}$ and the second is impossible. So

Each step is relevant with probability $a + b \ge K/m > 0$, independently, so $\Pr[R_t < \mathrm{Max}] \to 0$ as $t \to \infty$. $\square$

Theorem 2 (time and space). PROCESS takes $\Theta(K + P)$ time, given $\Theta(1)$ time for each random cell and each hash value, and the array has $m d$ bits.

Proof. Line L2 reads $K$ cells, line L3 chooses and updates $P$ cells, and line L4 writes $K$ cells. $\blacksquare$

The cells of a stable Bloom filter record the decay since the last set full

This proof shows: correctness, invariant, termination.

Write $C_t$ for the array after step $t$, and $V_t$ for the set of $P$ cells chosen at line L3 of step $t$. Each step does $K$ checks, $P$ decrements and $K$ sets, so it ends.

Lemma 1 (invariant (D)). For each $t \ge 0$ and each cell $j$, let $\tau = \max\{ s \le t : j \in H(x_s) \}$, if it exists. Then $C_t[j] = \max(0, \mathrm{Max} - |\{s : \tau < s \le t,\ j \in V_s\}|)$, and $C_t[j] = 0$ if $\tau$ does not exist.

Proof. By induction on $t$. At $t = 0$ all cells are 0 by line L1, and no element has arrived. Consider step $t + 1$ and cell $j$. If $j \in H(x_{t+1})$, then $\tau = t + 1$, there are no later decrements, and line L4 sets $C_{t+1}[j] = \mathrm{Max}$, after line L3. Otherwise $\tau$ is unchanged. If $j \in V_{t+1}$, the count of decrements grows by 1, and line L3 lowers the cell by 1 if it is above 0, which is the change of $\max(0, \mathrm{Max} - D)$ when $D$ grows by 1; and if $\tau$ does not exist the cell stays 0. If $j \notin V_{t+1}$, nothing changes. $\square$

Theorem 1 (what is reported). PROCESS$(x_t)$ returns true exactly when every $j \in H(x_t)$ was set at some step $\tau_j < t$ and had fewer than Max decrements in the steps $\tau_j + 1, \ldots, t - 1$, where $\tau_j$ is the last such step.

Proof. Line L2 reads $C_{t-1}$ before the decrements and sets of step $t$. By Lemma 1, $C_{t-1}[j] > 0$ exactly when $\tau_j \le t - 1$ exists and fewer than Max of the steps $\tau_j + 1, \ldots, t - 1$ chose $j$. $\square$

Corollary 1. If $x_t = x_{t-1}$, PROCESS$(x_t)$ returns true. More generally, if $x_t = x_s$ with $s < t$, and no cell of $x_t$ was chosen Max times in the steps $s + 1, \ldots, t - 1$, then PROCESS$(x_t)$ returns true.

Proof. Each $j \in H(x_t)$ was set at step $s$, so its last set $\tau_j$ satisfies $s \le \tau_j < t$, and it had at most as many decrements after $\tau_j$ as after $s$. For $s = t - 1$ there are no steps in between. Theorem 1 gives the claim. $\blacksquare$