Probabilistic Data Structures

Interactive visualizations of HyperLogLog, Balls-into-Bins, and the Hat Problem

HyperLogLog estimates the number of distinct elements using only $O(\log\log n)$ space. Each item is hashed, and we compute $\rho$ — the position of the leftmost 1-bit — like counting coin flips until heads ( $\Pr[\rho = k] = 2^{-k}$ ). The first $p$ bits select one of $m = 2^p = 16$ registers, each storing the max $\rho$ seen. Since $\max\{\rho\} \approx \log_2 n$ , the harmonic-mean estimator $\hat{n} = \alpha_m m^2 / \sum 2^{-R_j}$ recovers cardinality with relative error $\approx 1.04/\sqrt{m}$ .

Speed: 5/s

p = 4 (16 registers)

Estimated cardinality

Actual unique items

0 total insertions

Relative error

proof

Theoretical:

\approx 26.0\%

\frac{1.04}{\sqrt{m}} = \frac{1.04}{\sqrt{16}}

Space used

16 regs (10 bytes)

O(m) = O(2^p)

registers

HyperLogLog: Union & Intersection

HyperLogLog registers are mergeable: the element-wise max gives the sketch for the union. For intersection, we maintain bottom- $k$ MinHash sketches (the $k$ smallest hash values per server) to estimate Jaccard similarity, then compute $|A \cap B| \approx \hat{J}(A,B) \cdot |\widehat{A \cup B}|$ .

Server A

Recent items

No items yet

HLL Est.

Actual

MinHash

0/16

Bottom-k MinHash — Jaccard Similarity (k = 16)

Pair	Ĵ (MinHash)	J (actual)
Server A ∩ Server B	0.000	0.000

Union (HLL)

Actual: 0 · Error: 0%

hat{n}_{\cup} = \text{HLL}\!\bigl(\max_s R^{(s)}_j\bigr)

Intersection (Jaccard × Union)

Actual: 0 · Error: 0%

|A \cap B| \approx \hat{J}(A,B) \cdot \hat{n}_{A \cup B}

Intersection (incl-excl)

Actual: 0 · Error: 0%

\hat{n}_A + \hat{n}_B - \hat{n}_{A \cup B}