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.