Counting the crowd
A hundred thousand different customers and a 12 KB tally board. How far off is the count?
Ten stalls want one number a week: how many different people drank the chai. Writing every phone number down needs a book that grows with the crowd. The slate keeps tallies instead, each holding the longest lucky streak it has seen, and the lab counts a real crowd that way.
Board: The Slate Next to the Stove →On a narrow screen, the three readouts stack under the dials and the tally histogram comes last.
try this Step Tallies from 16 up to 16,384, then drag Different customers, and watch Typical miss against Memory.
The tallies say
99,740
true count 100,000, off by −0.26%
Typical miss
Memory
12 KB
the exact list: 781 KB
16,384 tallies miss by about 0.8%, in 12 KB. The exact list would need 781 KB, 65 times as much, and would be exactly right.
What the tallies hold
Each bar counts the tallies holding that longest run of heads (leading zeros in a customer's hash). Each doubling of the crowd moves the hump one step right.
A hundred thousand different customers and a 12 KB tally board. How far off is the count?
Luck, averaged out
One tally is one streak of luck. A single customer whose hash opens with twelve heads makes a crowd of one look like four thousand. Many tallies, each keeping its own longest run, outvote the lucky ones. The typical miss is 1.04 divided by the square root of the number of tallies, so four times the tallies halves the miss. Raise the tallies and the typical miss falls while memory climbs.
Memory stays fixed when you change the crowd. The tally board is the same size for a thousand customers or a million, while the exact list grows with every new face. Below about 1,500 customers the list is smaller, so store the names instead.
Limits of this model
The crowd is synthetic. Each customer is a number run through a fixed 32-bit mixing recipe, and "which crowd" changes a seed. A real HyperLogLog hashes real ids. The maths and the error are the same.
The exact list is a floor. It is counted at 8 bytes per customer, one 64-bit id each. A real exact set also spends memory on the table around the ids. Python's set for a million ids took 32 MB, four times the floor.
Memory is counted as Redis packs it, six bits per tally, so 16,384 tallies take 12 KB. The typical miss is the root-mean-square of the misses across eight crowds. It moves a little between dial settings, even where the formula says it should stay put.
This is the 2007 estimator, including the small-crowd fix. At two or three customers per tally it runs a little high: 4,096 tallies and 10,000 customers miss by about twice the expected error. Google's 2013 paper, HyperLogLog in Practice, corrects that range.