HyperLogLog counted billions of distinct items in kilobytes

Exact cardinality — how many distinct users, IP addresses or search queries have appeared — normally requires memory proportional to the number of distinct items, which is impossible at internet scale. In 2007 Philippe Flajolet and colleagues at INRIA published HyperLogLog, a probabilistic sketch that estimates cardinalities above a billion with about 2 percent accuracy using roughly 1.5 kilobytes of memory.

The trick rests on a coin-flip intuition: hash every element to a uniform random number and watch the longest run of leading zeros. A run of n zeros is rare — probability 2^-n — so when it appears, the set is probably large enough to have produced it, and 2^n is a good estimate of the cardinality. HyperLogLog splits the stream into many subsets, keeps one register per subset holding its longest zero-run, and combines them with a harmonic mean so outliers do not distort the estimate.

The method descended from Flajolet-Martin's 1984 algorithm and the LogLog algorithm. The engineering that made it production-ready came in the 2013 paper 'HyperLogLog in Practice' by Heule, Nunkesser and Hall at Google, which fixed bias and sparseness issues for large and small cardinalities.

Redis made HyperLogLog a product feature: its PFADD, PFCOUNT and PFMERGE commands estimate up to 2^64 distinct elements with up to 12 KB of memory per key and a standard error of 0.81 percent, and sketches merge so daily counts combine without re-reading the raw stream.

Estimate counts from hash leading zeros

A hash turns arbitrary data into a uniform random number with the same cardinality

The longest leading-zero run is a natural, observable estimate of set size

Splitting into registers plus a harmonic mean cancels the noise

Sketches merge, so daily counts combine without storing the raw stream

When the answer only needs to be approximate, stop storing the data — store a tiny sketch whose randomness reveals the size, and trade a bounded error for unbounded scale.

HyperLogLog became a standard building block in analytics and databases: Redis ships it as a data type, and the 2013 Google paper's improvements are what made it usable at scale in production systems. The sketch's logic — keep a small record of evidence, not the data — also anchors later structures like MinHash and Count-Min Sketch.