Sketching & Streaming

HyperLogLog

Count distinct items in a massive stream using a few kilobytes — by watching the rarest hash patterns.

Each bar is one register, holding the longest run of leading zeros seen among the hashes routed to it. The whole array — a few hundred small counters — is the entire memory; from it the distinct count is read off, never storing an item.

What you're seeing

How many distinct items has a stream contained — unique visitors, distinct search queries, separate IP addresses? Exactly, you'd need a set holding every item: gigabytes. HyperLogLog answers approximately in a few kilobytes by exploiting a quirk of randomness: hash each item to a random bit pattern, and the longest run of leading zeros you ever see is a fingerprint of how many distinct things you've hashed. Seeing a hash that starts with k zeros is a 1-in-2ᵏ event, so if the longest run is k, you've probably seen about 2ᵏ distinct items. To cut the wild variance of a single estimate, the first few bits of each hash route it to one of m registers, each tracking its own max run; combining them tames the noise. Watch the registers tick upward as the stream flows.

The rule

m = 2^p registers, all 0
add(x):
    h = hash(x)
    j = first p bits of h               # which register
    ρ = (leading zeros in the rest) + 1 # position of the first 1-bit
    register[j] = max(register[j], ρ)
estimate = α_m · m² / Σ_j 2^(−register[j])   # harmonic mean of m·2^reg

Adding the same item twice changes nothing (the max is idempotent), so it counts distinct items, and order doesn't matter — ideal for a stream.

The guarantee

HyperLogLog is unbiased with a tight, tunable error: the relative standard error is ≈ 1.04/√m, so quadrupling the registers halves the error. The estimator is a bias-corrected harmonic mean of the per-register estimates 2^register — the harmonic mean is the key trick, because it suppresses the registers that got unlucky with a freakishly long zero-run and would otherwise blow up an arithmetic average. With m = 16384 registers (16 KB) the error is about 0.8%, enough to count billions of distinct items on a budget that fits in cache. The headline cost is striking: estimating cardinalities up to N needs only O(m·log log N) bits — the "log log" that names the algorithm. Two honest caveats, both visible here: at small m the raw estimator is noticeably biased (the reason production HLL++ adds empirical bias correction), and at small cardinalities it switches to linear counting (using how many registers are still empty), which the demo does automatically.

The cost

per itemspaceerror HyperLogLogO(1)O(m·log log N)≈1.04/√m Exact setO(1)O(N·item)0

Each item is one hash and one max — O(1) time, independent of the count so far. The win is space, and it's enormous: the exact answer needs memory proportional to the number of distinct items (and their size), while HyperLogLog needs only one small counter per register regardless of N. Two HLL sketches can also be merged (take the per-register max) to count the union of two streams — perfect for distributed aggregation — though plain HLL can't directly intersect or delete.

In the wild

HyperLogLog is the standard answer to "count unique things at scale." Redis ships a PFCOUNT/PFADD HLL in a fixed 12 KB; Presto, BigQuery (APPROX_COUNT_DISTINCT), Spark, Druid, and Elasticsearch all use it for distinct-count queries over huge tables; and Google's refined HyperLogLog++ (2013) adds 64-bit hashing and bias correction. It descends directly from Flajolet–Martin and LogLog, and from the same lineage as the Morris counter — the founding idea of the whole sketching field: trade a little accuracy for an enormous space saving, and recover precision by combining many independent estimates.

Try this

Raise the precision p and watch the error in the readout fall by roughly half for each step (each step doubles m, and 1/√m improves as 1/√2). At the smallest p the estimate is visibly noisier and a touch biased — that's the regime where production systems lean on bias correction. Slide the distinct items down to a small number and the estimate stays sharp anyway: that's the linear-counting fallback quietly taking over.

References

  1. Flajolet, P., Fusy, É., Gandouet, O. & Meunier, F. "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm." AofA, 2007.
  2. Heule, S., Nunkesser, M. & Hall, A. "HyperLogLog in Practice…" (HyperLogLog++). EDBT, 2013 — 64-bit hashing and bias correction.
  3. Flajolet, P. & Martin, G. N. "Probabilistic counting algorithms for data base applications." JCSS 31(2), 1985 — the ancestor. And Andoni, Advanced Algorithms (Columbia, 2021). course materials.