Sampling, sketches and the ±1.6%

There are two ways to count how many distinct visitors a page had. Keep every identifier and count the list, or keep a structure that can estimate the answer without holding the members.

The first is exact, and the price is a table that grows with your traffic and contains one entry per person. That is a per-visitor record by another name, and it is the thing we set out not to keep.

The second is a probabilistic sketch. It answers “how many distinct” to within about one and a half per cent, from a few kilobytes, and there is no way to ask it whether a particular person was there. It has no membership test. There is nothing in it to erase.

One and a half per cent sounds like a lot until you compare any two analytics products measuring the same site on the same day. The difference between them will be larger, and neither of them mentions it.