How many distinct visitors did your website get today ? The obvious way is to keep a set of every visitor ID you have seen and ask for its size, but at the scale of billions of events that set would swallow gigabytes of memory. HyperLogLog (Flajolet et al., 2007) performs the same count, distinct elements in a massive stream, using a few kilobytes, by giving up exactness for a tiny, controllable error. Its secret is a delightful piece of probability : rare coincidences betray how many things you have seen. If this trade, sacrifice exactness to save enormous space, sounds familiar, it is the same bargain struck by Bloom filters, and the two are cousins in the family of probabilistic data structures.
1. The problem : counting distinct things is expensive
Counting events is trivial : keep one integer and increment it. Counting distinct events, the cardinality of a set, is the hard part, because to know whether the ID you just saw is new, you seemingly must remember every ID seen so far. Exact cardinality of $n$ distinct items needs $O(n)$ memory. HyperLogLog breaks that barrier.
2. The coin-flip intuition
Here is the whole idea in a game. Ask a friend to flip a coin repeatedly and remember only the longest run of heads they ever saw at the start of a flip-sequence. If they report a run of $3$ heads, you can guess they did not flip many times ; if they report a run of $20$, they must have been flipping for ages, because a run of $20$ heads is astronomically rare ($\text{probability } 2^{-20}$).
HyperLogLog plays exactly this game with hashes. Each item is hashed to a random-looking binary string. We look at the position of the first $1$ bit, equivalently, the number of leading zeros. A hash beginning with $\rho$ zeros is as rare as flipping $\rho$ heads in a row (probability $2^{-\rho-1}$). So if, across the whole stream, the most leading zeros we ever saw is $\rho$, a good bet is that we have processed roughly $2^{\rho}$ distinct items.
3. From a wild guess to a good estimate
A single “max leading zeros” is an absurdly noisy estimator, one lucky hash with many zeros throws it off by a factor of two. The fix is stochastic averaging : split the stream into $m$ independent groups (registers) using the first few bits of each hash to choose a group, and track the maximum $\rho$ within each register separately. Now we have $m$ noisy estimates instead of one, and we can average them.
The crucial invention of HyperLogLog is how to average 1 : not the arithmetic mean, but the harmonic mean of the per-register estimates, which tames the outliers that a few large registers would otherwise cause. The cardinality estimate is
\[\begin{equation} \hat{n} = \alpha_m\, m^{2} \left( \sum_{j=1}^{m} 2^{-M[j]} \right)^{-1}, \label{eq:hll} \end{equation}\]where $M[j]$ is the maximum leading-zero count in register $j$ and $\alpha_m$ is a small bias-correction constant ($\alpha_m \approx 0.7213/(1 + 1.079/m)$).
4. Why it is astonishing
The accuracy of HyperLogLog is governed by the number of registers : the relative error is about
\[\begin{equation} \frac{\sigma}{n} \approx \frac{1.04}{\sqrt{m}}. \label{eq:err} \end{equation}\]In plain words : quadrupling the number of registers halves the error. Each register only needs to store a small integer (a count of leading zeros, at most $\sim 6$ bits). With $m = 16{,}384$ registers that is roughly 12 KB of memory, and $\eqref{eq:err}$ gives an error under $1\%$, while counting cardinalities into the billions. An exact set would have needed gigabytes. That gap, kilobytes versus gigabytes, is why HyperLogLog is built into Redis (the PFADD / PFCOUNT commands), Presto, BigQuery, Redshift and countless analytics pipelines.
5. A family resemblance
It is worth pausing on how similar this is to Bloom filters. Both start by hashing items into random-looking bits ; both keep a small fixed-size summary instead of the data ; both answer a question approximately, with a mathematically guaranteed error, that would otherwise cost linear memory. They differ in the question : a Bloom filter answers “have I seen this exact item ?” (membership), while HyperLogLog answers “how many different items have I seen ?” (cardinality). Together they are the two most famous members of a toolbox every large-scale engineer should know.
6. Conclusion
HyperLogLog turns a childhood observation, that stumbling on a rare coincidence means you have tried many times, into a rigorous cardinality estimator. Hash each item, watch the leading zeros, spread the observations across many registers, and combine them with a harmonic mean : a few kilobytes then suffice to count billions of distinct things to within a percent, in one pass, and the sketches even merge for free. It is a small monument to how a clever dose of randomness can buy enormous savings, the same lesson its cousin the Bloom filter teaches, applied to a different question.
References
- Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm. Conference on Analysis of Algorithms (AofA), 137–156.
@inproceedings{Flajolet2007, author = {Flajolet, Philippe and Fusy, {\'E}ric and Gandouet, Olivier and Meunier, Fr{\'e}d{\'e}ric}, title = {HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm}, booktitle = {Conference on Analysis of Algorithms (AofA)}, pages = {137--156}, year = {2007} }
-
HyperLogLog is the last in a lineage : Flajolet–Martin (1985) introduced the leading-zeros idea, LogLog (Durand & Flajolet, 2003) added registers, and HyperLogLog (Flajolet et al., 2007) added the harmonic mean. Google’s HyperLogLog++ (Heule et al., 2013) later refined the small-range bias and memory layout used in practice. ↩