Counting the crowd without a register (HyperLogLog, count-min, top-k)

The Slate Next to the Stove · Open board

The slate by the stove, and its second curse: the slate is small. This lesson asks it a question it has no room to answer by writing names down. The lab at the end of the story runs the counter.

Before you start. You need the stall from The chai stall that got famous (load balancing), which got famous and became ten stalls, and the slate from The slate next to the stove (caching): a small board by the stove that holds a few lines and then runs out of room. From Hashing you need one idea: a fixed recipe that stirs any input into a jumble of digits, the same jumble every time for the same input. The second read also uses a heap from Trees (BST, balancing, heaps, tries), a pile that hands you its smallest item first.

The idea in 30 seconds

Counting different visitors exactly needs memory that grows with the crowd, because every visitor must be remembered to spot repeats.
HyperLogLog estimates that count in fixed memory: it turns each visitor into a fixed random-looking pattern (a hash), and each of many small counters (registers) keeps the longest run of zeros seen at the start of a pattern, so repeats change nothing.
Its typical error is 1.04 divided by the square root of the number of registers, so four times the memory halves the error; Redis uses 16,384 registers, 12 KB, 0.81%.
Two HyperLogLogs merge by taking the larger value in each register, which counts the union without double-counting anyone.
A count-min sketch, a small grid of counters that many items share, estimates how often each item appears; its guesses can be too high but never too low, and a short list beside it keeps the top-k, the k most frequent items.
Count exactly for money, for names, for small crowds, or when items must be deleted.

Read the story · Skip to the numbers