Twelve Kilobytes Will Count a Billion Different Things

Last timeTotals in Bounded Memory

An exact distinct count needs every value you have seen. An estimate within one per cent needs a fixed twelve kilobytes, and the reasoning that gets you there is worth following once.

What a sketch is doing

The last lesson left an exact count of distinct values in the impossible

column: to know whether an arriving value is new, you must have kept every

value you have seen.

Give up exactness and the problem changes completely. Every sketch makes the

same two moves, and recognising them is most of understanding any of them.

The first move is to hash. Replace each item with the hash of the item, which

is a value that looks uniformly random and, crucially, is the same every time

the same item arrives. That second property is the one doing the work. A

repeated item produces an identical hash, so whatever statistic you keep of the

hashes cannot be affected by repetition. Duplicates become invisible without

anything having to remember that they were duplicates.

The second move is to keep a statistic of the hashes that depends on how many

distinct ones there were, and to keep only that statistic. The hashes

themselves are thrown away as they arrive.

Counting by the rarest thing seen

Here is the statistic, and it is strange enough to be worth deriving rather

than accepting.

Look at a uniform hash in binary. The chance it begins with a zero is a half.

Two zeros, a quarter. Three zeros, an eighth. In general, a run of k zeros at

the front happens about one time in two to the k.

Now turn that round. If you have been watching hashes go past and the longest

run of leading zeros you have ever seen is k, how many distinct hashes have you

probably drawn? Something in the region of two to the k, because that is how

many draws it typically takes to see a pattern that rare.

FIG 1The estimate from one observation

: estimated number of distinct items
: the longest run of leading zeros seen in any hash

The entire algorithm, in one line, using one small integer of storage. Note what it does not contain: any term for how many items arrived, any term for duplicates, and any record of what was seen. A run of eleven leading zeros suggests about two thousand distinct items whether those arrived in a minute or over a year, and whether each appeared once or a million times.

FIG 2Watching the longest run grow

step	item	its hash begins	leading zeros	longest so far	estimate	what happened
1	first visitor	0101...	1	1	2	One leading zero, which is entirely unremarkable, and the estimate is accordingly tiny and useless.
2	second visitor	0001...	3	3	8	Three zeros is a one in eight pattern, so having seen it suggests a handful of draws. Still noisy, still in the right direction.
3	the first visitor again	0101...	1	3	8	The same item hashes to the same value, so nothing changes. This is the whole reason the sketch does not need to remember anything: repetition is a no-op by construction.
4	a later visitor	00000001...	7	7	128	A one in a hundred and twenty-eight pattern has appeared, so the estimate jumps to about that many distinct items. The jumping is the problem with using a single estimator, and the fix is the next section.

4 steps

Two things to take from this. The third row is the mechanism that makes duplicates free, and it costs nothing because it is a property of hashing rather than a feature anybody implemented. And the estimate moves only in powers of two, by a factor of two at a time, which makes a single estimator far too crude to report. It is unbiased in a loose sense and has an enormous variance, which is exactly the situation that averaging fixes.

Trading room for error

A single estimator is useless and the repair is the obvious one: run many

independent copies and average them.

You cannot simply hash each item several times, because that costs time and the

copies would not be cheap. The trick used in practice is to split instead. Take

the first few bits of the hash as a bucket number, and use the rest of the hash

for the leading-zero count within that bucket. With fourteen bits of bucket you

have sixteen thousand three hundred and eighty-four buckets, each one holding

one small integer, each one seeing roughly one sixteen-thousandth of the

distinct items and forming its own estimate.

Combining them with a harmonic mean rather than an arithmetic one, which damps

the effect of a single wild bucket, and applying a constant correction, gives

the estimator that is deployed everywhere.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents