HyperLogLog

Estimates the number of distinct items seen in a stream using only 2p tiny registers, whether the stream has a thousand or a trillion events.

How it works

Every item is hashed to a long, effectively-random bit string. The first p bits select one of 2p registers (buckets). The rest of the bits are scanned for their position of leftmost 1-bit, call it ρ (rho). Each register keeps the maximum ρ ever routed to it.

Why does that estimate cardinality? A run of k leading zeros in a uniformly random bit string has probability 2-k. So if a bucket's register holds ρ=5, it's a signal that roughly 2⁵ distinct hashes have landed in that bucket: long runs are rare, so seeing one implies many draws. Averaging (via a harmonic mean, per the original paper, to stay robust to outlier registers) across all 2p registers turns these per-bucket signals into one cardinality estimate.

More registers (higher p) means a longer-and-more-precise estimate at the cost of memory: standard error scales as 1.04/√(2^p). Redis's PFCOUNT and BigQuery's APPROX_COUNT_DISTINCT are built on this exact idea (with the HLL++ refinements from Google's follow-up paper for small and huge cardinalities).

The register array never changes across estimators, only the formula that turns it into a number does. The demo below lets you switch between the raw harmonic mean (no bias correction), the HLL++-style estimate above (empirical small/large-range correction), and LogLog-Beta (Qin, Kim, Leung, 2016), which replaces the empirical correction with a single closed-form polynomial "beta function" of the count of empty registers, needing no lookup table or piecewise cases across the whole cardinality range.

Interactive demo

Estimator
Registers (m)16
True distinct count0
Estimate0.00
Error vs. truthn/a

Standard error for this precision: ±26.00%. Add more distinct items to see the estimate converge toward the true count. Switching estimators recomputes the estimate from the same register array shown below; it does not change what was recorded.

No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new HyperLogLog(p)Allocate 2^p single-byte registers.O(2^p) space
add(item): voidUpdate the max-rho register for item's bucket.O(1) time
rawEstimate(): numberHarmonic-mean estimate with no bias correction.O(2^p) time
estimate(): numberCardinality estimate via harmonic mean + small/large range correction.O(2^p) time
loglogBetaEstimate(hll): numberLogLog-Beta closed-form bias correction over the same registers.O(2^p) time
standardError(): numberApproximate relative standard error, 1.04/√m.O(1)

References

Original papers

Library implementations

Real-world use cases