Probabilistic Data Structures — Counting Without Counting

Bloom filters, HyperLogLog and the Count-Min sketch explained from zero — how giving up the right to always be correct buys you memory that never grows, and how large services actually operate these sketches.

Space/Time Trade-offs in Hash Coding with Allowable Errors (Bloom

The moment you try to count, you run out of memory

"How many people visited the site today?" The honest answer is easy: put every visitor ID into a set and check its size at the end. At a thousand visitors a day, nothing about this is a problem.

At a hundred million a day, with the same number demanded per hour, per country and per article, everything changes. You now need memory proportional to the number of sets. The same problem shows up in "have I already processed this URL?" and "which IP is hammering us right now?" Answer any of them honestly and you end up remembering everything you have seen.

Probabilistic data structures — usually called sketches — relax that requirement in exactly one place: they allow the answer to be wrong once in a while. What you get in return is memory that does not grow no matter how much data flows through. A HyperLogLog costs 12 KB per aggregate. Twelve kilobytes for a hundred million people, twelve kilobytes for ten billion, with under 1% error.

"Counting exactly" is just another name for "remembering everything"

Why does relaxing one requirement change things by orders of magnitude? The reason sits below the algorithms, in the amount of information involved.

To answer "is it in the set?" for $n$ distinct keys without ever being wrong, you must retain enough information to distinguish that set from every other possible set — which means keeping something equivalent to the keys themselves. But the moment you say "I will tolerate answering yes for something absent with probability $\varepsilon$," the lower bound on the bits you need drops to this:

Here $n$ is the number of elements stored and $\varepsilon$ is the false-positive rate you accept. In words: $\log_2(1/\varepsilon)$ bits per element is enough — about 6.6 bits at 1% error, about 10 bits even at 0.1%. The crucial detail is what is missing from the formula: the length of the key never appears. A 100-byte URL and a 1 KB search query both cost a handful of bits. Tolerating error is a licence to throw away the key itself and keep only a trace of it.

The question you are asking determines which of three tools you want.

All three are built on hash functions. A hash erases the structure in your input — sequential IDs, near-identical URLs — and makes anything look like a random bit string, and the statistics ride on top of that "looks random" property. How hash functions themselves are constructed is covered in Hashing and Nearest-Neighbor Search.

What follows takes the three in turn, down to why counting works at all without counting.

Bloom filters: saying "no" with certainty

All you need is an array of $m$ bits (all zero to start) and $k$ hash functions. To insert, run the element through the $k$ hashes and set the $k$ bits they point at. To query, look at those same $k$ positions: if even one is zero, the element is definitely absent; if all are one, it is "probably present." The element itself is never stored.

False negatives are impossible by construction — a bit that has been set never goes back. False positives happen when bits set by other elements happen to cover all $k$ positions. After inserting $n$ elements, the false-positive rate is:

The term $1 - e^{-kn/m}$ is the probability that a given bit has been set by somebody, and $p$ is the probability that all $k$ of them have. Raising $k$ makes a full house less likely but fills the array faster, so there is an optimum: at $k = (m/n)\ln 2$ exactly half the array ends up set. Ten bits per element buys you a false-positive rate just under 1%. The derivation and a compact implementation live in Randomized Algorithms.

Line that up against the bound from earlier and something interesting appears. At $\varepsilon = 1\%$ the bound was 6.6 bits per element; a Bloom filter spends 10. In other words it burns roughly 44% more memory than the theoretical optimum. What it buys with that inefficiency is a structure that runs on nothing but bit operations. Cuckoo filters and quotient filters close much of the gap and support deletion, by storing a short fingerprint of each element instead of anonymous bits. A plain Bloom filter cannot delete because clearing a bit would also erase every other element sharing it, manufacturing the false negatives that were supposed to be impossible.

There is also a usage pattern worth internalising: a Bloom filter is not a standalone answer but a gatekeeper placed in front of an expensive check. If it says "no," you skip the expensive work entirely; only when it says "yes" do you consult the real store. A false positive costs one wasted lookup, and correctness is still guaranteed by the store behind it — so the probabilistic error never reaches the user.

The remaining two — HyperLogLog for how many distinct, Count-Min for how many times — replace bit-setting with small statistics. Why does staring at the leading zeros of a hash reveal a crowd size? Why does taking a minimum leave you with overcounting as your only failure mode? That, and how large services actually run these things, is what follows.