HyperLogLogOpen in Colab

HyperLogLog

HyperLogLog (HLL) estimates the number of distinct elements (the cardinality) of a stream using memory that grows only doubly-logarithmically in the count — a few kilobytes to count billions, within a couple of percent. It is the production successor to the Flajolet-Martin sketch and powers COUNT(DISTINCT …) in Redis, Presto, BigQuery, and Druid.

Recap: the Flajolet-Martin trailing-zero idea

Hash each element to a uniform bit string and let ρ(x)\rho(x) be the position of the leftmost 1 (equivalently, one plus the number of leading zeros). Because bits are uniform, Pr⁡[ρ(x)≥k]=2−k\Pr[\rho(x) \geq k] = 2^{-k}: seeing a hash with kk leading zeros is a 2−k2^{-k} event, so if the largest ρ\rho observed is RR, there were probably on the order of 2R2^{R} distinct values. Duplicates hash identically and never change RR, so the estimate tracks distinctness, not volume.

A single such estimator has enormous variance — one lucky hash with many leading zeros throws it off by a factor of 2. HLL's contribution is a principled way to average many estimators cheaply.

Stochastic averaging: split into registers

Use the first pp bits of each hash to pick one of m=2pm = 2^{p} registers; apply the ρ\rho trick to the remaining bits and keep the maximum in that register:

j=⟨b1…bp⟩2,M[j]←max⁡ ⁣(M[j],  ρ(bp+1bp+2… )).j = \langle b_1 \dots b_p \rangle_2, \qquad M[j] \leftarrow \max\!\big(M[j],\; \rho(b_{p+1} b_{p+2}\dots)\big).

This is like running mm independent Flajolet-Martin estimators (one per register) but each element updates exactly one of them, in O(1)O(1) time. Each register holds a small integer (the max ρ\rho seen), so the whole sketch is mm registers of ~6 bits: a few KB for m=4096m = 4096.

The estimator: a harmonic mean

Averaging the per-register estimates 2M[j]2^{M[j]} with a harmonic mean (which suppresses the heavy upper tail that inflates a plain average) gives the HLL cardinality estimate:

n^  =  αm m2(∑j=1m2−M[j])−1,\widehat{n} \;=\; \alpha_m \, m^2 \left( \sum_{j=1}^{m} 2^{-M[j]} \right)^{-1},

where αm\alpha_m is a bias-correction constant:

α16=0.673,α32=0.697,α64=0.709,αm≈0.72131+1.079/m  (m≥128).\alpha_{16}=0.673,\quad \alpha_{32}=0.697,\quad \alpha_{64}=0.709,\quad \alpha_{m}\approx \frac{0.7213}{1 + 1.079/m}\ \ (m \geq 128).

The relative standard error is

σn≈1.04m.\frac{\sigma}{n} \approx \frac{1.04}{\sqrt{m}}.

So m=1024m = 1024 registers give ~3.25% error, m=4096m = 4096 give ~1.6%, and doubling accuracy costs only 4× the (already tiny) memory.

Range corrections

The raw estimator is biased at the extremes, so HLL patches both ends:

  • Small range (n^≤52m\widehat n \leq \tfrac{5}{2}m): if VV registers are still zero, switch to linear counting, n^=mln⁡(m/V)\widehat n = m \ln(m/V), which is accurate when the sketch is sparsely populated.
  • Large range (near the hash space, e.g. n^>130232\widehat n > \tfrac{1}{30}2^{32} for 32-bit hashes): correct for hash collisions with n^=−232ln⁡(1−n^/232)\widehat n = -2^{32}\ln(1 - \widehat n/2^{32}). Modern HLL++ uses 64-bit hashes (making this correction essentially unnecessary) plus an empirical bias table and a sparse representation for small cardinalities.

Worked trace

Take m=4m = 4 registers (p=2p = 2 bits), all initialised to 0, and stream four distinct hashes (leading register-select bits in brackets):

hashregister bitsremaining bitsregister jjρ\rho (pos. of leftmost 1)MM after
[01]000101…01000101…14[0,4,0,0]
[11]010…11010…32[0,4,0,2]
[01]0001…010001…14 (no change)[0,4,0,2]
[00]1…001…01[1,4,0,2]

One register is still 0, so V=1V = 1 and the small-range rule applies: n^=mln⁡(m/V)=4ln⁡4≈5.5\widehat n = m\ln(m/V) = 4\ln 4 \approx 5.5. The raw harmonic-mean formula would instead give α4⋅16/(2−1+2−4+20+2−2)=0.673⋅16/1.8125≈5.9\alpha_4 \cdot 16 / (2^{-1} + 2^{-4} + 2^{0} + 2^{-2}) = 0.673\cdot 16 / 1.8125 \approx 5.9 — both near the true count of 4, and the corrections keep them honest as the register array fills. (See the notebook for the full estimator run to millions of distinct items.)

Watch it run

The same four hashes, bit by bit, then a check of the error formula the whole design rests on:

HyperLogLog — leading zeros, stochastic averaging, and 1.04/√m

1/7

Four registers (p = 2 bits of the hash select one), all starting at zero. The idea underneath: hash bits are uniform, so a hash with k leading zeros is a 2⁻ᵏ event. If the rarest thing you have seen is a 1-in-2ᴿ event, you have probably seen about 2ᴿ distinct values — and duplicates hash identically, so they never move the estimate.

python
1def add(M, x, p):
2 h = hash(x) # uniform bits
3 j = h >> (32 - p) # first p bits
4 tail = (h << p) & 0xffffffff
5 rho = leading_zeros(tail) + 1
6 M[j] = max(M[j], rho)
7
8def estimate(M, m):
9 Z = sum(2.0 ** -v for v in M)
10 n = alpha(m) * m * m / Z # harmonic mean
11 V = M.count(0)
12 if n <= 2.5 * m and V > 0:
13 return m * log(m / V) # linear counting
14 return n
state
registers M (max ρ seen per register)
M[0]
0
M[1]
0
M[2]
0
M[3]
0

One such estimator has ruinous variance — a single lucky hash doubles it. Splitting the stream across m registers and averaging is HLL's actual contribution.

The m = 4 worked trace from above, hash by hash: register-select bits, ρ from the remaining bits, and a register that refuses to move when a duplicate arrives — which is what makes this a distinct count rather than a total. The final step measures the RMS error of real sketches at five register counts against the 1.04/√m prediction the whole design rests on — averaged over replicates, because a single sketch at any m proves nothing.

What to notice as you step:

  • The duplicate changes nothing. The third hash lands on register 1 with the same ρ\rho it already holds, so max is a no-op. That is the entire reason this counts distinct elements: re-seeing a value can never move a register.
  • Only the maximum is kept per register, never a count. The sketch has no idea how many elements it has seen — just how rare the rarest hash was.
  • The small-range rule fires here, because one register is still zero. The raw harmonic estimator and linear counting disagree (5.9 vs 5.5) and the correction picks the one that is trustworthy in this regime.
  • The last step measures 1.04/m1.04/\sqrt{m} across replicate sketches, because it is a standard error — one sketch at m=16m = 16 can beat one at m=1024m = 1024 by luck, and only averaging shows the trend.

Gotchas

  • Hash quality is everything. Bits must be uniform and independent; a weak hash biases ρ\rho and wrecks the estimate.
  • Mergeable. Two HLL sketches combine by taking the element-wise max of registers — perfect for distributed/parallel counting and for unions. Intersections are not directly supported (use inclusion-exclusion, which amplifies error).
  • Cardinality only. HLL answers "how many distinct," never "is xx present" (that's a Bloom filter) or "how frequent is xx" (Count-Min).

See also

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Referenced by
HyperLogLogStreaming Algorithms & Sk…