Proofs: Xor filter

The false positive rate of an xor filter full

This proof shows: complexity.

Model. Assume ideal hashing: in each try, $h_0, h_1, h_2$ and $\mathrm{fp}$ are independent random functions, with $h_j$ uniform on block $j$ and $\mathrm{fp}$ uniform on $\{0, \ldots, 2^r - 1\}$, and the tries use independent functions.

Theorem 1. For each key $x \notin S$, $\Pr[\text{QUERY}(x) = \text{true}] = 2^{-r}$.

Proof. Let $T$ be the try at which BUILD stops. Whether a try succeeds depends only on the cells of the keys of $S$ in that try, so $T$ is independent of the values at $x$ of the functions of all tries. The table $B$ is a function of the cells and fingerprints of the keys of $S$ in try $T$. Given $T = t$ and all the values on $S$, the values $h_0(x), h_1(x), h_2(x), \mathrm{fp}(x)$ of try $t$ are still independent and uniform, since $x \notin S$. So the xor $w = B[h_0(x)] \oplus B[h_1(x)] \oplus B[h_2(x)]$ is independent of $\mathrm{fp}(x)$, and

Theorem 2 (time and space). QUERY takes $\Theta(1)$ time: four hash values and three cell reads. Each try of BUILD takes $\Theta(n + \ell)$ time, which is $\Theta(n)$. The table has $3\ell r$ bits, with $3\ell \le 1.23 n + 35$.

Proof. Lines L6 and L7 visit each key and each cell once. In lines L8 and L9 each cell enters the queue at most once at line L7 and once for each time its count falls to 1, which is at most once for each key that uses it, so the queue has at most $3\ell + 3n$ entries in total, and each is handled in constant time. The loop of lines L4 and L5 has $n$ steps of constant time. The bound on $3\ell$ follows from $\ell \le (1.23 n + 32)/3 + 1$. With Theorem 2 of the correctness proof, the expected time of BUILD is $\Theta(n)/p$, which is $\Theta(n)$ whenever the success probability $p$ of a try is bounded below by a constant, as it is at this table size for large $n$ by the threshold result of Molloy (2005). $\blacksquare$

An xor filter accepts every key of its set full

This proof shows: correctness, invariant, termination.

Let $S$ be a set of $n$ distinct keys. For fixed hash functions write $E(x) = \{h_0(x), h_1(x), h_2(x)\}$, a set of three distinct cells, one in each block.

Lemma 1 (peeling order). If PEEL$(S)$ succeeds, its order $(x_1, c_1), \ldots, (x_n, c_n)$ lists each key of $S$ once, and for each $t$, $c_t \in E(x_t)$ and $c_t \notin E(x_{t'})$ for each $t' > t$.

Proof. Call a key remaining while it is not yet in the order. Lines L6 and L9 keep, for each cell $c$, the count and the xor of the indices of the remaining keys $y$ with $c \in E(y)$: line L6 sets them for all keys, and line L9 removes a key from its three cells when it leaves. When line L8 takes a cell $c$ with count 1, exactly one remaining key uses $c$, and the xor is its index. That key $x_t$ is appended and stops being remaining. So $c_t \in E(x_t)$, each key is appended at most once, and the keys $x_{t'}$ with $t' > t$ were remaining at that time and are not $x_t$, so they do not use $c_t$. Success at line L10 means all $n$ keys are listed. $\square$

Lemma 2. In the loop of lines L4 and L5, the cell $c_t$ is written only at step $t$, and after step $t$ no cell of $E(x_t)$ is written.

Proof. Step $t'$ writes only $c_{t'}$. For $t' > t$, $c_t \notin E(x_{t'})$ by Lemma 1, while $c_{t'} \in E(x_{t'})$, so $c_{t'} \ne c_t$. The steps after step $t$ are the steps $t' < t$, and they write $c_{t'}$, which is not in $E(x_t)$ by Lemma 1 applied to $t'$ and the later index $t$. $\square$

Theorem 1 (invariant (X) and no false negatives). After BUILD, $B[h_0(x)] \oplus B[h_1(x)] \oplus B[h_2(x)] = \mathrm{fp}(x)$ for each $x \in S$, so QUERY$(x)$ returns true.

Proof. Take $x = x_t$, and let $u, v$ be the two cells of $E(x_t)$ other than $c_t$. Line L5 sets $B[c_t] = \mathrm{fp}(x_t) \oplus B[u] \oplus B[v]$, so right after step $t$, $B[c_t] \oplus B[u] \oplus B[v] = \mathrm{fp}(x_t)$, since $a \oplus a = 0$. By Lemma 2 none of the three cells changes after step $t$. Line L11 then computes the same xor. $\square$

Theorem 2 (termination). Under ideal hashing, with a fresh independent choice of hash functions in each try, BUILD ends with probability 1, and the number of tries has a geometric distribution.

Proof. Each try succeeds with the same probability $p$, independently. It remains to show $p > 0$, by one choice of the cells that peels. Since $3\ell \ge 1.23 n + 32$, we have $3(\ell - 1) \ge n$, so we can give each key $x$ a private cell $\pi(x)$, all distinct, using at most $\ell - 1$ cells of each block, and keep one spare cell $z_j$ in each block $j$. Let the other two cells of $x$ be the spare cells of the two other blocks. Then each $\pi(x)$ has count 1 and is in the first queue, and peeling removes the keys one after another, so it succeeds. This choice of cells has positive probability under ideal hashing. Each try is $O(n)$ steps, since each key leaves the queue at most once. $\blacksquare$