Spending correctness: what a sketch is

At what exchange rate do sketches trade correctness?

The first structures that spend a new currency

In Lookup structures and Ordering structures, every design moved cost around inside a closed system. There were three currencies (read, write and space amplification), one triangle between them, and each structure was a point inside it. Nothing you did changed the total.

This article is the first that spends a currency from outside the triangle. It trades correctness. The return is not a better constant factor. It is a change in the complexity class of the state. Counting the distinct values in a stream exactly provably needs space proportional to n (written Ω(n); you must remember each value, or you cannot tell if the next one is new). HyperLogLog does it in O(m log log n) space and answers within 1% from about 12 KB, for any n you will ever see. That is not an optimization of the exact algorithm. It is a different algorithm that answers a slightly different question, and the gap between the two questions is where all the space went.

The framing that makes the whole article one idea instead of eleven tricks:

A sketch is a small summary of a big data set that can answer one kind of question approximately. In every case below you hash the item, keep a summary statistic of the hashed values, and estimate the answer from that statistic. A Bloom filter projects a key onto k bit positions. Count-Min projects a frequency table onto d rows. HyperLogLog projects onto one register per bucket and keeps a maximum. MinHash keeps a minimum. The error you get is set by the variance of the estimator, and the standard error falls as 1/√m when you have m independent observations. That gives the exchange rate for the entire article. We call it the Approximation law:

This is the central limit theorem (the statistics result that averages of many random values cluster tightly around the true mean) appearing as a budget line. It is not a systems result. It is statistics constraining design. But the practical consequence is not obvious: sketches are extremely cheap at moderate accuracy and very expensive at high accuracy. That is the opposite of exact structures, where accuracy is free once you hold the data and space grows linearly. The two cost curves cross, and the crossing point can be computed for any given n and error ε. Below the crossing point, use a sketch. Above it, store the data.

Two corrections to state first, because both are widely believed and both are wrong.

These structures are not "fuzzy". A Bloom filter is an exact bit array whose read operation has a known, one-sided, computable error rate. The error is characterized, not unknown. You get a contract of the form "with probability 1 − δ, the answer is within ε", and you can build a system on a contract. You cannot build one on "approximately".

The error is a property of the question, not of the data. Count-Min's error is proportional to the total size of the stream, not to the size of the item you asked about. So it is accurate for heavy hitters and useless for the tail by construction, not by bad settings. Almost every sketch has a clause like this, and almost every sketch failure in production is someone asking the sketch a question that its statistic does not preserve.

An exact structure stores the data and answers any question. A sketch stores one statistic and answers one question. The space saving is the price of every other question you can no longer ask.

Two classifications to carry through this article

One-sided versus two-sided error

• Bloom, cuckoo and XOR filters have false positives (they say "maybe present" for something absent) and never false negatives (they never say "absent" for something present). This asymmetry makes them safe as guards: a negative answer is authoritative, so you can skip an I/O with certainty, and a positive answer costs one wasted I/O and nothing else. The error costs work, never correctness.
• Count-Min only overestimates. Misra-Gries only underestimates.
• HyperLogLog and the quantile digests are two-sided and unbiased: the error can go either way and averages to zero.

The design rule follows directly: put one-sided structures where a wrong answer costs only work, and two-sided structures where the answer was going to be approximate anyway. Never put a two-sided sketch anywhere that a false negative would silently drop data.

Idempotent versus counting. This is rarely stated, and it is operationally the most important property in the article. A structure is idempotent if inserting the same value twice changes nothing.

• Idempotent: Bloom filter, HyperLogLog, Theta sketch, MinHash. They keep maxima, minima or set bits, so a second copy of an item changes nothing.
• Counting (not idempotent): Count-Min, Misra-Gries, Space-Saving, t-digest, reservoir sample. Inserting twice changes the answer.

The consequence concerns delivery guarantees in pipelines. A message system with at-least-once delivery may deliver the same record twice after a retry, a replayed partition or a duplicated batch. Exactly-once delivery needs extra machinery to prevent that. For the idempotent sketches, at-least-once delivery is effectively exactly-once: duplicates do not corrupt a distinct count. Counting sketches have no such protection and require exactly-once machinery or deduplication upstream. If you remember one thing from this article for operations, remember this: check whether your sketch is idempotent before you decide how much you care about your delivery guarantee.