HyperLogLog

A counter of distinct things that keeps none of them. It answers “how many different?” to within about a percent, using an amount of memory that does not grow with the answer.

Where this is actually used

Redis ships this as a built-in type, and Google, Presto and Elasticsearch all use it. Counting unique visitors with an exact set costs memory proportional to the visitors; HyperLogLog counts them in about 12 KB whether there were ten thousand or ten billion.

The guarantee

alwaysA register value never decreases.
boundedThe estimate can miss in either direction, by about one standard error.σ ≈ 1.04/√m

How it works

It stores no items. It keeps the longest run of leading zeros seen in each register, reasons that long runs are rare, and counts distinct values from that.

Flajolet, Fusy, Gandouet & Meunier, AofA 2007

Start hereMultiply the stream length by ten and watch two numbers: the estimate follows the true count up, and the memory figure does not move at all. That is the entire trick.

Parameters

the entire memory cost, one byte each, no matter how many items arrive

m — registers

p=12 · m=4,096 · 4.0 KiB

Registers are always a power of two, since the index comes from the top p bits of the hash. Four times the registers halves the error.

Stream

Distributionhow often items repeat — real data is never uniformDistinct items, no repeats. The worst case for fill ratio at a given m.

Distinct itemshow many different items exist to draw fromStream lengthhow many items go through the structureSeedchanges the hash, and therefore which items happen to collide

The link carries the stream and every parameter. No server, no account — the state travels in the URL.

Readings

Running…