← Back

Interactive Article

HyperLogLog

Approximates distinct-element counts with a fixed, tiny amount of memory using probabilistic hashing — and sketches merge cleanly, which makes it a great fit for large streaming data.

Counting how many distinct things you've seen sounds easy until the stream is huge: unique visitors, distinct search queries, addresses touched by a scan. Exact counting means remembering every item you've seen, so memory grows without bound. HyperLogLog estimates the same count in a few kilobytes, flat, no matter how many billions of items flow through.

Feed the sketch below. Add elements one at a time, or pour in a thousand random ones, and watch the estimate track the true distinct count while the memory — 16 little registers — never grows.

0
actual distinct
0
HLL estimate
—
error
16 registers · each stores max leading-zero rank
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

The core trick

Hash each item to a random-looking bit string and look at the run of leading zeros. A hash starting 1… happens half the time; 01… a quarter; 001… an eighth. So seeing a hash with k leading zeros is a hint that you've probably seen around 2^k distinct items — rare patterns only tend to show up once you've drawn a lot of samples.

Tracking the single longest run is wildly noisy, though: one lucky item throws the whole estimate off. HyperLogLog tames that variance by splitting the stream into many buckets.

Buckets and the harmonic mean

Use the first few bits of each hash to pick one of m registers, and use the rest to compute the leading-zero rank. Each register keeps only the maximum rank it has ever seen — that's why re-adding the same item changes nothing, and why the whole sketch is just m small numbers.

To estimate the total, HyperLogLog combines the registers with a harmonic mean (which suppresses outliers), scales by m², and multiplies by a bias-correction constant:

E = α_m · m² / Σ 2^(−register[j])

More registers means lower variance. The standard error is about 1.04 / √m, so 16 registers (this demo) wobble a fair bit, while 16,384 registers — a common production choice — land within ~1% using roughly 12 KB. Small counts also get a linear-counting correction, which is why early estimates here stay sharp.

Why it scales

Two properties make HyperLogLog a workhorse for analytics. It's fixed-size: the sketch for a thousand items and a billion items occupy the same bytes. And it's mergeable: to union two sketches, take the element-wise maximum of their registers — so you can count distinct values across shards or time windows by combining precomputed sketches, with no re-scan.

That's why it's baked into Redis (PFADD/PFCOUNT), Presto, BigQuery, and Druid: approximate COUNT(DISTINCT) over enormous data, cheaply, with an error bar you can reason about.