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 be the position of the leftmost 1 (equivalently, one plus the number of leading zeros). Because bits are uniform, : seeing a hash with leading zeros is a event, so if the largest observed is , there were probably on the order of distinct values. Duplicates hash identically and never change , 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 bits of each hash to pick one of registers; apply the trick to the remaining bits and keep the maximum in that register:
This is like running independent Flajolet-Martin estimators (one per register) but each element updates exactly one of them, in time. Each register holds a small integer (the max seen), so the whole sketch is registers of ~6 bits: a few KB for .
The estimator: a harmonic mean
Averaging the per-register estimates with a harmonic mean (which suppresses the heavy upper tail that inflates a plain average) gives the HLL cardinality estimate:
where is a bias-correction constant:
The relative standard error is
So registers give ~3.25% error, 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 (): if registers are still zero, switch to linear counting, , which is accurate when the sketch is sparsely populated.
- Large range (near the hash space, e.g. for 32-bit hashes): correct for hash collisions with . 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 registers ( bits), all initialised to 0, and stream four distinct hashes (leading register-select bits in brackets):
| hash | register bits | remaining bits | register | (pos. of leftmost 1) | after |
|---|---|---|---|---|---|
[01]000101… | 01 | 000101… | 1 | 4 | [0,4,0,0] |
[11]010… | 11 | 010… | 3 | 2 | [0,4,0,2] |
[01]0001… | 01 | 0001… | 1 | 4 (no change) | [0,4,0,2] |
[00]1… | 00 | 1… | 0 | 1 | [1,4,0,2] |
One register is still 0, so and the small-range rule applies: . The raw harmonic-mean formula would instead give — 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
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.
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 it already holds, so
maxis 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 across replicate sketches, because it is a standard error — one sketch at can beat one at by luck, and only averaging shows the trend.
Gotchas
- Hash quality is everything. Bits must be uniform and independent; a weak hash biases 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 present" (that's a Bloom filter) or "how frequent is " (Count-Min).
See also
- Streaming Algorithms & Sketches: the lesson this deep-dive expands
- Flajolet-Martin, Bloom filters, and DGIM in the same lesson