HyperLogLog
Counting distinct items normally costs memory proportional to how many there are; HyperLogLog counts billions in a couple of kilobytes by never storing a single one of them.
“How many unique visitors did we have?” is one of those questions that sounds cheap and is not. Done exactly, it means holding every distinct identifier you have ever seen. At web scale that is gigabytes to answer a question whose result is a single number.
HyperLogLog answers it in kilobytes, and the trick is that it never stores an item at all.[1]paperHyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
The intuition
Hash each item to a uniformly random bit string. In random data, a hash starting with one
leading zero turns up about half the time; two leading zeros a quarter of the time; k
leading zeros about one time in 2^k.
So run it backwards. If the longest run of leading zeros you have ever seen is 10, you have probably looked at something like 2¹⁰ distinct values. The maximum run length is a crude estimate of the logarithm of the cardinality - hence the name.
Hashing is also what makes duplicates free: the same item always produces the same hash and never moves the maximum. The structure is counting distinct values without ever needing to know which ones it has seen.
Why one counter is not enough
A single maximum is a terrible estimator - one unusually lucky hash early on poisons it
permanently. HyperLogLog fixes this by splitting the hash: the first few bits pick one of
m registers, and the rest supply the run length for that register.
That gives m independent estimates. Averaging them damps the luck. Crucially it uses the
harmonic mean, which is much less sensitive to a single large outlier than the
arithmetic mean, plus a bias-correction constant.[1]paperHyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
estimate = α(m) · m² / Σ 2^(-register[i])The property that makes it useful
The standard error is 1.04/√m. Read that carefully: it does not contain the
cardinality.
1024 registers gives about 3% error whether you are counting a thousand items or a billion. Memory is fixed at deploy time by the accuracy you choose, and never grows.
Drop the register count to 16 in the widget and the expected error jumps to 26%; push it to 1024 and it settles near 3%. The item count makes almost no difference to either.
The other property, and the one that made it infrastructure rather than a curiosity: two sketches merge by taking the element-wise maximum of their registers. Counting unique visitors per server and combining them afterwards gives exactly the same answer as counting centrally. Exact distinct counts cannot do that without shipping the sets around.
Where the plain algorithm falls down
The estimator misbehaves at small cardinalities, when most registers are still zero. Flajolet’s paper handles this by switching to linear counting below a threshold, and Google’s production work replaced the correction with an empirically calibrated bias table plus a sparse representation for small sets.[2]paperHyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm Redis implements that sparse-then-dense approach, which is why a Redis HLL holding a handful of items costs far less than the full 12KB.[3]source codeRedis - hyperloglog.c
The dial
The line - when someone asks
HyperLogLog estimates how many distinct items a stream contained by hashing each one and tracking, per bucket, the longest run of leading zeros seen - a long run is unlikely, so seeing one implies many distinct items. It takes the harmonic mean across buckets to damp the outliers, giving a standard error of 1.04/√m that depends only on the number of registers, not on the cardinality. You use it when an approximate count of a huge set is worth far more than an exact count you cannot afford to compute.
Recall
Loading…
Where are you with this?
Saved on this device. Sign in to keep it across devices.
Sources
Primary
- [1]
- [2]
Secondary
- [3]