HyperLogLog

Why it matters

"How many unique visitors did this page get today" is an innocent question that is brutal at scale: exact counting needs a set of every visitor id, gigabytes per metric, multiplied by every page, every window and every dimension you want to slice by, and sets from different servers must be unioned. HyperLogLog answers within about 1 percent using 12 KB per counter, merges by taking a maximum, and is why analytics systems can offer unique counts for anything. It is one of the most elegant ideas in practical computer science and a favourite interview question.

The idea

Hash every item to a uniformly random bit string. In a random bit string, the probability that the first set bit appears at position p is 1 over 2 to the p. So if, among all the distinct items you have seen, the longest run of leading zeros is about 20, you have probably seen about 2 to the 20, a million, distinct items. Duplicates hash identically and change nothing, which is what makes it count distinct rather than total.

That single estimate is wildly noisy, one unlucky hash doubles it. HyperLogLog fixes it by splitting the stream into m registers using the first b bits of the hash (m equals 2 to the b, typically 16,384), tracking the maximum leading-zero count in each register, and combining the m estimates with a harmonic mean, which tames outliers. Error is about 1.04 divided by the square root of m: about 0.8 percent at 16,384 registers, which at 6 bits per register is 12 KB.

Corrections that make it practical

Small cardinalities (fewer items than registers) are estimated badly by the formula, so implementations switch to linear counting (count empty registers) at the low end; very large ones hit hash-collision limits with 32-bit hashes, so 64-bit hashes are used. Redis stores small sets in a sparse encoding of only the non-zero registers and switches to the dense 12 KB form as they fill, so counting ten items costs bytes, not kilobytes. HyperLogLog++ adds bias correction tables for the mid range.

Merging

The union of two sets is estimated by taking, register by register, the maximum of the two sketches. The result is exactly the sketch you would have built from the combined stream. So per-server sketches merge at an aggregator, per-hour sketches merge into days, and per-page sketches merge into a site total, all without ever seeing the raw ids. Intersections are not directly supported; they are estimated via inclusion-exclusion with much worse error, so if you need "users who did A and B", keep separate exact sets or a different structure.

Where it lives

Redis PFADD, PFCOUNT and PFMERGE are HyperLogLog. Every analytics warehouse offers approximate distinct counts (APPROX_COUNT_DISTINCT, HLL_COUNT) built on it; many store sketches as columns so unique counts can be re-aggregated across any dimension later. Observability systems use it for unique series and unique hosts; databases use it in query planners to estimate distinct values for a column.

Question	Structure
How many distinct items?	HyperLogLog
How many times did this item occur?	Count-Min sketch
Is this item present?	Bloom or cuckoo filter
Which items are most frequent?	Count-Min plus a top-k heap
How similar are two sets?	MinHash, next lessons