The answer that is allowed to be wrong

Two hundred thousand requests arrive at a service. How many distinct clients were there?

Written down like that it is not a hard question. Keep a hash set, insert every client identifier, report its size at the end. On the stream measured throughout this essay that set would hold 23,925 entries, and holding them exactly — a 32-bit key and a counter wide enough for the most frequent — takes 1,124,475 bits, which is 137 kilobytes for a question whose answer is five digits long.

That is the whole of the field. The exact answer is available and its cost is proportional to the data rather than to the answer; the approximate answer costs 5,120 bits and is out by 2.7%.

What is different about this field #

Every algorithm measured on this site so far was checked before it was measured. A sort that does not leave its array sorted is not a slow sort, it is an error, and the counted array throws rather than reporting its counts — the check that has caught more implementation mistakes here than any other single line. The reason it can be applied at all is that correctness is on offer. The algorithm is given its input, it is allowed as many passes over it as it likes, and there is a right answer it either produces or does not.

Take away the second of those and the first goes with it. If the data goes past once and there is not room to keep it, then at the moment the stream ends the algorithm holds a few hundred bits and is being asked about a hundred thousand items. Most of the information is gone. Whatever it says is a guess informed by what it chose to keep, and the design question is not whether the answer is wrong but how wrong, how often, and what the bits bought.

So there are two quantities on every plate in this field, and neither of them is a running time:

The state, in bits. Not slots, not entries, not objects — bits, counted from the shape of the structure. At this end of the scale the difference between a five-bit register and a thirty-two-bit one decides whether a summary of a million streams fits in a cache, and a count of “entries” hides it entirely.

The error, against exact truth. Computed by a hash map the summary never sees, on the same stream, in the same run. Not against a bound, not against a formula, not against another estimate.

The second is worth dwelling on, because it is where this kind of writing usually goes wrong. A structure with an error bound of $\varepsilon$ is not a structure with an error of $\varepsilon$. The bound is a promise about the worst case at some confidence; the error is a number the run produced. Quoting the first and calling it the second is the field’s characteristic mistake, and the guarantee that is one query wide is about how far apart the two can get.

The eighth counter #

The site has counted seven things: comparisons, cache misses, auxiliary slots, random bits, branch mispredictions, block transfers, and bits emitted by a coder. The eighth is bits of state held while the stream runs, and the case for it being a new counter rather than a rename is that the existing space counter cannot express it.

The space counter measures scratch space, and it measures it beside an input. Merge sort’s buffer is $n$ slots on top of an array of $n$ that is already in memory; quicksort’s recursion is $\log n$ frames beside the same array. The interesting quantity there is the ratio, which is what “sorts in place” is a claim about, and in place is a claim is the essay that pins the three behaviours that phrase covers.

Here there is no array to be beside. The state is not the overhead, it is the entire memory the algorithm has, and the input never occupies any of it. A structure holding 5,120 bits is holding 5,120 bits whether the stream was a thousand items or a billion, and that constancy is the property being bought. Expressing it as a ratio against $n$ would report a number that falls to zero and says nothing.

One pass, and it is enforced #

The model’s defining restriction is that the data can be read once, in order, and not again. It is also the restriction easiest to violate by accident, because a second for loop over the same array looks exactly like the first one and produces better numbers.

So it is not described here, it is enforced. Every summary in this field is fed through a wrapper that yields the items once and throws on any second iteration, with a message that names the model rather than the mechanism: a summary that can rewind is not a streaming algorithm, and its state bound is a statement about nothing. The check is one of the ones that must be able to fail, and the gate feeds it a second pass and requires the refusal.

That the restriction is real rather than decorative shows up in what the structures cannot do. None of them can be asked a question that was not designed into it. A cardinality estimator holding 320 bits cannot tell which keys they were; a frequency sketch cannot list the keys it saw, only answer about ones it is handed. Every summary is a lossy projection chosen in advance, and choosing it is the design.

Why the answer cannot be exact, and it is not a matter of cleverness #

The natural response to a structure that is wrong is to look for a better one. It is worth settling early that there is not one, because the argument is short and it is the same argument this site’s first floor is built on.

The floor under every comparison sort counts outcomes: a comparison sort must be able to distinguish $n!$ orderings, each comparison distinguishes two cases, so no such sort makes fewer than $\log_2(n!)$ comparisons. The floor here counts memory states instead. An exact distinct-counter must reach a different state for every half-sized subset of its universe, because two subsets that reach the same state give the same answer after one more key is appended, and their true answers differ. So the state needs at least $\log_2 \binom{u}{u/2}$ bits, which is $u$ minus about half of $\log_2 u$ — linear in the universe, and nothing about the algorithm changes it.

That is a floor on the exact answer. It says nothing about approximate ones, and the whole field lives in the gap: allowing a 2% error and a 1-in-50 chance of missing it takes the requirement from linear in the universe to a few thousand bits, permanently, however large the stream gets. The floor under a summary develops both halves.

The exchange rate, measured #

The hero figure is the shape of the trade, and the shape is the finding. Every estimator drawn there sits on a slope near $-\tfrac12$: quartering the error costs sixteen times the bits. Nothing forced them to agree — they are unrelated structures, one keeping registers, one keeping hashes, one keeping a bitmap — and the agreement is the measurable content of “the space bound is $\Theta(1/\varepsilon^2)$”.

It is worth reading that slope the other way round. A structure on a slope of $-\tfrac12$ has diminishing returns of a very specific kind: the first factor of two in accuracy is cheap and the fourth is not. At 320 bits a HyperLogLog is out by 11%; at 5,120 bits, sixteen times the state, it is out by 3.4%. Going to 0.85% would take 81,920 bits, and at that point the exact hash map is within a factor of fourteen and answers a great many more questions.

That is the honest frame for the whole field: these structures are not a way to get accurate answers cheaply. They are a way to get inaccurate answers at a cost that does not grow.

The site has met one trade of this shape before. A Bloom filter buys a false-positive rate with bits per element, and there the exchange rate is not a slope but a constant overhead against a floor that can be written down exactly.

The stream is part of the claim #

One more thing has to be stated before any number in this field means anything, and it is the same discipline the external-memory field applies to its $B$ and $M$: the input distribution is a parameter, and it is printed on every plate.

Two streams are used throughout. The first is all distinct — every item a key never seen before — which is the cleanest test of a cardinality estimator, because the true answer is the length of the stream and is known by construction rather than counted afterwards. The second is Zipf with exponent 1.1 over a stated universe, which is the input every frequency claim is made on.

Zipf is not an arbitrary choice and it is not neutral. On the 60,000-item stream used by the frequency essays, the single most common key accounts for 16% of everything that went past, the ten most common for 43%, and 836 of the 3,528 distinct keys occurred exactly once. A summary of a stream shaped like that is doing something specific: it is spending its bits on a small number of keys that carry most of the mass, and getting the rest badly wrong.

That is worth saying plainly because it cuts both ways. On a uniform stream — every key equally likely, no heavy hitters at all — a frequency sketch has nothing to concentrate on and its estimates are uniformly poor. The structures in this field are not general-purpose; they are built for skew, deployed where skew is expected, and their published accuracy figures are measured where it is present. A claim about a sketch with no stated stream is the same kind of claim as a complexity class with no stated input distribution, and what O-notation does not say is the essay that names the problem in its original setting.

A single run is an anecdote #

The estimators here are randomised, and this site has a standing rule about randomised things: the distribution is the result and a single number is a draw from it. Expected is not average makes the case in the setting where it is easiest to see, and it applies without modification here.

The practical form of the rule is that every accuracy claim in this field is made over many seeds. An estimator that happened to land within 1% on one stream with one seed has demonstrated nothing; the same estimator over sixty seeds has a spread, and the spread is what a caption can quote.

The other half: counting things that are not distinct #

Cardinality is the cleanest question to open with because its answer is one number. The other half of the field asks about frequencies — how often did this particular key occur, and which keys were the frequent ones — and it has a different shape, because a summary of a stream that can be interrogated about arbitrary keys must have compressed all of them into the same few thousand bits.

Two structures answer that question in this field and they are wrong in opposite directions, which is worth flagging now because it is the most useful single fact in it. The randomised sketch never returns a count below the truth. The deterministic counter table never returns one above it. Neither is the general case of the other, and at equal state the deterministic one is more accurate on the question both are usually asked — a result the items that survive k counters measures rather than argues.

The error at which the field runs out #

The observation that the exact map is “within a factor of fourteen” at 81,920 bits invites the obvious next question, and it has an answer: at what error does the approximate structure stop being smaller than the exact one?

The two costs are known. The exact map on this stream is 1,124,475 bits. The estimator is 5,120 bits at 3.4%, on a slope near $-\tfrac12$, so its state is $5{,}120 \times (3.4/\varepsilon)^2$.

Set them equal. The two curves meet at $\varepsilon \approx 0.23\%$ on an exact half-power slope, and at about 0.35% on the slope the two measured points actually give — 320 bits at 11% and 5,120 at 3.4% is an exponent of $-0.42$ rather than $-0.50$. Either way: somewhere between a quarter and a third of a per cent, approximation stops paying.

That number is the field’s right-hand edge and it is closer than the framing suggests. The usable band on this stream runs from 11% at 320 bits down to about 0.25%, which is under two orders of magnitude of error bought with roughly twelve doublings of state — and the reason published accuracies cluster around one or two per cent is that this is the middle of a short range rather than a point anybody optimised to.

The comparison is also generous to the estimator in a way worth stating. The exact map answers which keys, how many times each, and every question nobody thought of in advance; the sketch answers one. So the crossing above is where the sketch stops winning on the only axis it can win on, and a system that wants a second question from the same bits has already crossed.

But the edge moves, and the direction is the whole argument for the field. The exact cost is proportional to the number of distinct keys; the estimator’s is not. Double the cardinality and the map doubles while 5,120 bits stay 5,120 — so the crossing error falls as the square root of the stream’s cardinality, since the estimator needs $\varepsilon^{-2}$ bits to reach it.

Put a number on that. On a stream of a hundred times this one’s cardinality — two and a half million distinct clients rather than twenty-four thousand — the crossing is at 0.023%, and the usable band has widened by a factor of ten at its narrow end. The estimator has not improved; the thing it is being compared against has grown.

Which is the honest statement of what these structures are for, sharper than the one three paragraphs above. They are not a way to get inaccurate answers at a cost that does not grow — that phrasing makes the fixed cost sound like the point, and a fixed cost is only valuable relative to something rising. They are a way to make the accuracy a system can afford improve as the stream gets larger, at half a bit of error per doubling of cardinality, while the exact structure gets steadily more expensive to hold.

And it explains why a twenty-four-thousand-key stream is a poor advertisement for the technique. At that size the exact answer costs 137 kilobytes, which any machine has; the interesting regime is the one where it costs gigabytes, and the crossing is somewhere no application would ask for. The floor under a summary is the argument that nothing better than $\varepsilon^{-2}$ is available; this is the arithmetic saying where that exponent stops mattering, and it is further out than the plate can draw — the same limitation one pass, k slots has about its own reservoir.

The exchange rate does not move with the stream #

Before the stream is varied it is worth isolating the two estimators whose slopes are supposed to differ, because a plate with three lines on it hides which of them is doing the work.

The trade above is one cardinality, and the useful property of these estimators is that the same bits buy the same relative error however many distinct keys there are.

Forty times the other way is the reading that matters to a deployment, because it is the direction a stream actually grows in and the direction an exact counter cannot follow.

What none of those three shows is the budget axis taken past where the opening plate stopped, and a slope is a claim about a range.

What this field is not #

Three exclusions, stated here so that the later essays do not have to keep restating them.

Nothing here is timed. The unit is the bit and the error, exactly as the unit in the external-memory field is the block transfer. Throughput is a real property of these structures and a real reason they are deployed, and it is a property of an implementation on a machine rather than of the algorithm — the count is not the time is the site’s standing position and it holds here.

Nothing here is a sample. A summary and a sample are different objects: a sample of a stream answers questions nobody designed for and is wrong in a way that gets better with more data, and a sketch answers exactly the questions it was built for and is wrong in a way that gets better with more bits. One pass, k slots is the sampling side of the same restriction, and the two essays are neighbours rather than rivals.

The bounds here are not proved. They are quoted where the literature has them, and what is measured is whether the structures climb the shape those bounds describe. A finite measurement can refute an asymptotic claim and can measure the constant the notation drops; it cannot establish a limit, and a limit is not a prediction is where that position is set out.

What the field is for #

The reason to spend a phase on this is not that approximate counting is a nice trick. It is that this is the only field on the site where the answer is a designed quantity rather than a discovered one.

Everywhere else the algorithm produces the right answer and the design question is what it costs. Here the design fixes the cost first — a fixed number of bits, decided before the stream starts — and the answer is whatever those bits can support. Accuracy becomes a resource, purchasable, tradeable against space, and subject to floors of its own.

That inversion is what makes the field worth its name. It also makes the site’s habit sharper rather than looser: with no exact answer to check against, the only thing separating a working summary from a broken one is a measurement against a truth computed elsewhere — which is why every plate in this family carries both, and why the gate for this field is the one that breaks a sketch on purpose and requires the assertions to notice.