Proofs: Flajolet-Martin sketch

The one-bitmap Flajolet-Martin estimate is within a constant factor full

This proof shows: complexity.

Take one bitmap, $m = 1$, with $L$ larger than any index that occurs below. Assume ideal hashing: the values $h(x)$ of distinct items are independent and uniform $w$-bit integers, with $w$ large. Then for each item, $\Pr[\rho(h(x)) = r] = 2^{-(r+1)}$, independently over the items. Let $n$ distinct items be seen and let $R$ be the index of the lowest 0 bit.

Lemma 1. $\Pr[B[r] = 1] = 1 - (1 - 2^{-(r+1)})^n$.

Proof. By Lemma 1 of the correctness proof, $B[r] = 0$ exactly when no item has $\rho = r$. Each of the $n$ independent items avoids $r$ with probability $1 - 2^{-(r+1)}$. $\square$

Theorem. For each integer $a \ge 0$,

In particular, for $c$ a power of two with $n/c$ a power of two, $\Pr[2^R \ge cn] \le 1/c$ and $\Pr[2^R < n/c] \le e^{-c}/(1 - e^{-c})$.

Proof. Upper tail. If $R \ge a$ with $a \ge 1$, then $B[a-1] = 1$, which by Lemma 1 and Bernoulli's inequality $1 - (1 - p)^n \le np$ has probability at most $n 2^{-a}$. For $a = 0$ the bound $n \ge 1$ is trivial.

Lower tail. If $R < a$, then $B[r] = 0$ for some $r < a$. By Lemma 1, $1 - p \le e^{-p}$ and the union bound, this has probability at most $\sum_{r < a} e^{-n 2^{-(r+1)}}$.

The special case. Take $2^a = cn$ in the upper tail. For the lower tail take $2^a = n/c$. The term $r = a - 1 - l$ is $\exp(-c \, 2^{l})$, and $2^l \ge 1 + l$, so the sum is at most $\sum_{l \ge 0} e^{-c} e^{-cl} = e^{-c}/(1 - e^{-c})$. $\square$

So for $c = 4$ the estimate $2^R$ lies in $[n/4, 4n)$ with probability at least $1 - 1/4 - 0.019 > 0.73$. The constant factor $1/\varphi$ and the averaging over $m$ bitmaps make this a relative error of $O(1/\sqrt{m})$; Flajolet and Martin (1985) proved the exact constants $\varphi = 0.77351$ and $0.78/\sqrt{m}$.

Cost. ADD computes one hash, one division by $m$, one count of trailing zeros and one bit write, which is $\Theta(1)$ word operations on the word RAM. ESTIMATE scans at most $L + 1$ bits of each bitmap, $O(mL)$ steps. The space is $mL$ bits. $\blacksquare$

The Flajolet-Martin sketch is a function of the set of distinct items full

This proof shows: correctness, invariant, termination.

For an item $x$ let $j(x) = h(x) \bmod m$, $q(x) = \lfloor h(x)/m \rfloor$, and call $x$ recorded if $q(x) > 0$ and $\rho(q(x)) < L$; then let $r(x) = \rho(q(x))$. For a set $A$ of items define the bitmaps $\Sigma(A)$ by

Lemma 1 (invariant). After the items $a_1, \ldots, a_t$ have been added, the bitmaps equal $\Sigma(\{a_1, \ldots, a_t\})$.

Proof. By induction on $t$. For $t = 0$ line L1 gives all zeros, which is $\Sigma(\emptyset)$. Let the claim hold for $t$ and let $A = \{a_1, \ldots, a_t\}$ and $x = a_{t+1}$. Line L3 computes $j(x)$ and $q(x)$, and line L4 sets bit $r(x)$ of $B_{j(x)}$ if $x$ is recorded, and does nothing otherwise. No bit is cleared. So the new bitmaps have a 1 exactly at the 1s of $\Sigma(A)$ and, if $x$ is recorded, at $(j(x), r(x))$. This is $\Sigma(A \cup \{x\})$. $\square$

Theorem.

1. The state, and so the output of ESTIMATE, depends only on the set of distinct items seen, not on their order or their number of repeats.
2. The bitwise OR of the sketches of two streams with the same $m$, $L$ and $h$ equals the sketch of the concatenated stream.
3. $R_j$ is the least $r \in \{0, \ldots, L\}$ such that $r = L$ or $B_j[r] = 0$, and ESTIMATE returns $(m/\varphi) 2^{S/m}$ with $S = \sum_j R_j$.
4. Each operation ends: ADD takes a constant number of steps, and ESTIMATE scans at most $L + 1$ positions of each of the $m$ bitmaps.

Proof. Claim 1 is Lemma 1, since $\Sigma(A)$ depends only on $A$. For claim 2, the definition gives $\Sigma(A \cup A') = \Sigma(A) \lor \Sigma(A')$ bit by bit, because "some recorded $x \in A \cup A'$" is "some recorded $x \in A$ or some recorded $x \in A'$". Claims 3 and 4 follow from lines L5 to L7 and the definition of $R_j$. $\blacksquare$