The model a bound was quoted in

The previous phase of this field measured a dozen summaries and produced perhaps forty accuracy figures. Every one of them was a measurement under four assumptions, and not one of the plates said so.

The data arrives once and in one direction. Every update is an insertion. Nothing ever expires. And the hash functions behave as though drawn uniformly from all functions.

None of those is a detail. Each is a model, in the sense that a bound’s truth is conditional on it, and this essay is what each one is worth — measured, one dial at a time.

Dial one: an update may be negative #

Count-Min’s estimate is never below the truth. The proof is that a cell is a sum of non-negative counts, so it contains the queried key’s own count plus a non-negative pile.

The condition is on the frequency vector at query time and not on the updates. Deletions that never take a count below zero — the strict turnstile — preserve it exactly, and the theorem holds unchanged. Deletions that may take a count below zero do not.

The third row is the interesting one. That stream is in the general model — 216 keys end with a negative count — and Count-Min was above the truth on every one of the 200 heavy keys queried, because the violation was in the tail and the queries were not.

So the model is violated and the symptom is absent, and the symptom returns in the fourth row not because anything about the structure changed but because the queries started touching keys the violation reached. A test written against the heavy hitters would report this structure healthy in a model where its guarantee has no force at all.

Dial two: a count may end negative #

The distinction between the strict and general turnstiles is the one most often collapsed, and the previous section is why it should not be.

It is also the dial with the clearest engineering reading. A count of things currently present is a strict turnstile quantity by construction — sessions open, items held, rows in a partition — because nothing is removed that was not first added. A count of differences is not: subscribing to two feeds and sketching one minus the other produces negative counts by design.

The two situations are written with the same code and differ in a property of the data that no structure can check.

Dial three: items expire #

Turn on expiry and nothing from the first phase works at all.

An exact counter cannot answer a windowed question — not because it is too small but because it discarded the arrival times. Neither can a Count-Min sketch, a HyperLogLog, or a quantile summary. This is the only one of the four dials that changes what a structure has to be rather than how well it does, and the structures for it are new constructions rather than old ones re-examined.

It also comes with the phase’s only lower bound: an exact windowed count needs $W$ bits, performed exhaustively rather than quoted. Approximation escapes it — an exponential histogram is 1,656 bits at a window of eight thousand — and that escape has a crossing point at a window of a thousand for a 10% tolerance, below which the approximation is larger than the exact answer.

Dial four: the hash family #

The fourth assumption is the one that is written down most often and examined least: let $h$ be chosen uniformly at random from all functions.

No summary uses such a function; one would take twenty-five gigabytes to write down. What is used is a family with a degree — the number of keys at a time over which its values are jointly uniform — and the two halves of an estimator’s analysis consume different amounts of it. The tug-of-war estimator’s mean needs two and its variance needs four.

The measured consequence of buying too little:

The bottom row is the shape worth carrying. A family too weak does not produce obviously wrong answers and does not widen its error bars. It produces answers that are approximately right and a structure whose accuracy stops responding to its size — sixteen times the state for a fifth of the improvement, and worse at 640 registers than a proper family at forty.

The dials are not independent #

It is tempting to read the four as a checklist and they interact, in one direction that matters.

Expiry forces a choice about the other three. The obvious way to implement a window is to add each arrival and subtract it $W$ arrivals later, which turns a window into a turnstile — and then the first two dials are on as well. That construction is common, it works, and it converts a structure with a one-sided guarantee into one without, silently, as a side effect of a decision about time.

A weak hash and a violated model are indistinguishable from the outside. Both produce a structure returning plausible numbers whose errors do not behave as documented. The first shows up as an accuracy that stops improving with state; the second as an error in a direction the guarantee forbids. Neither announces itself, and a system exhibiting one will usually be diagnosed as the other, or as bad data.

The one dial with a floor under it is the one that cannot be worked around. Signed updates, negative counts and a weak hash all have repairs that cost a constant factor. Expiry costs $W$ bits for an exact answer and there is a proof, so the only escape is approximation — which is a different kind of concession from the other three.

Where the four dials leave the ledger #

It is worth writing down what each dial does to each structure, because the pattern is not what a reader would guess from the structures’ reputations.

Two readings. The randomised linear structures are portable: their state is a sum, so signs and cancellation are free, and they pay for it by depending on a hash family whose properties have to be argued. The deterministic structures are each valid in exactly one model and depend on no randomness at all — their guarantees are theorems with no probability in them, and their reward for that is having nowhere else to go.

That is a genuine trade rather than a ranking, and it is the sharpest thing this phase has to say about how to choose. Portability across models and freedom from assumptions about randomness are the two ends of the same axis, and no structure in this field has both.

Four ways a correct bound misleads #

Collecting this phase’s findings, there turn out to be four distinct failures and they are worth separating, because the repairs differ.

The bound is quoted in a model the data is not in. Count-Min’s one-sidedness under general-turnstile updates. The bound is true, the data is outside its scope, and the structure cannot tell. The repair is a declaration checked against the data.

The bound is quoted against the wrong quantity. Count-Min’s error is $\varepsilon \lVert f\rVert_1$ of the net vector, and the natural reading of “$\varepsilon$ times the length of the stream” is the gross traffic. On a stream that cancels 94.9% of what goes past, those differ by 19.6 times and the quoted guarantee is twenty times too pessimistic. The repair is naming the norm.

The bound is about a quantity nobody wanted. A quantile summary’s promise is on the rank, and a reader of the answer wants the value. On a heavy tail a 0.10% rank error is a 1,553% value error, and both numbers are correct descriptions of the same answer. The repair is measuring the quantity the reader has in mind, and reporting both.

The bound is loose in a way it does not report. Count-Min’s per-query failure probability was measured in the previous phase at zero against a permitted 1.8%; its magnitude bound is 2,548 here against a measured worst of 1,971 and a typical 325. There is no repair; the bound is doing its job, and the measurement is the only thing that reports the slack.

The first three are avoidable and the fourth is not. All four look identical from inside a system that is producing plausible numbers.

The fifth dial nobody in this phase turned #

For completeness, and because leaving it out would be the same omission this essay is about: there is a fifth assumption behind every measurement here, and it is the one the previous phase did enforce.

One pass. Every structure in both phases is fed through a wrapper whose second iteration throws, because an algorithm allowed two passes is not a streaming algorithm and its state bound describes nothing. It is the assumption easiest to violate by accident — a second for loop over the same array looks exactly like the first — and the one whose violation most flatters the result, since a second pass buys accuracy at no apparent cost in state.

It is left off the dial list above because nothing in this phase varies it. A multi-pass model is a real and well-studied setting with its own bounds, and every claim made across these twenty essays is a claim about one pass.

The honest way to hold all five together: a summary’s guarantee is a function of five things about the input — how many passes, whether updates may be negative, whether counts may end negative, whether items expire, and what is true of the hash family. Four of them are properties of the data and one is a property of the algorithm’s own randomness, and none of the five is visible in the number a query returns.

The sixth dial: whether the input may depend on the answers #

There is one more assumption behind every figure in both phases, it is stronger than the five above, and it is the only one that can be violated by a system that never touches the data.

Every bound here is proved against an input fixed in advance. The randomness is drawn, the stream arrives, and the stream does not know what the structure decided. That is an oblivious adversary, and it is what “with probability $1-\delta$ over the choice of hash” quietly means: the probability is over the hash, for each fixed input, and it says nothing about an input chosen after the hash has started answering.

A great many deployments are not oblivious, and they become non-oblivious by ordinary engineering rather than by attack. A sketch that decides which keys to sample more finely feeds its own estimates back into what arrives next. A cache admission policy driven by a frequency sketch changes the traffic the sketch then sees. A dashboard that triggers a retry storm when a percentile crosses a line has made the stream a function of the summary’s answers. In each case the input at time $t$ depends on outputs the structure produced before $t$, and the analysis has no purchase on any of it.

The failure mode is specific and worth stating, because it is not “the error gets a bit larger”. A structure whose randomness is fixed at construction has, in effect, one draw for its entire life. An input that reacts to its answers is performing a search over that one draw’s blind spots, and the search does not need to be malicious or even deliberate — a feedback loop that preferentially amplifies whatever the sketch overestimates will find the overestimated keys by construction. That is the adversary who knows the seed arriving without an adversary, and the repairs are the ones that essay names: fresh randomness, or a structure whose guarantee survives adaptivity.

So this dial differs from the other five in what it is a property of. The five are properties of the data — how it arrives, what it contains, how many times it is read. This one is a property of the system the structure is embedded in, and no amount of examination of the stream reveals it. A recorded stream replayed in a laboratory is oblivious by construction, which means the only setting where the assumption is easy to check is the one setting where it is guaranteed to hold.

What the declaration check cannot do #

The machinery below computes a stream’s model from the stream and refuses a mismatch, which is the right design and is worth being precise about the limits of, on the same principle the essay applies to everything else.

It computes the model from a sequence that already exists. In a laboratory the whole stream is in hand before anything is measured, so the computation is available and the check is exact. In production the stream has not happened yet, and the property being checked — whether any count will ever end negative, whether the arrival order is adversarial — is a statement about the future.

So a deployed system cannot run this check; it can only carry an assertion about its source, made by whoever knows what the source is. That assertion is worth writing down for exactly the reason the whole essay exists: an unwritten assumption is one nobody revisits when the source changes, and sources change more often than structures do. A sketch sized for a cash-register stream that is later fed a diff between two feeds has had its model changed by a decision made somewhere else entirely, in a system that has no idea a guarantee depended on it.

The check that is available in production is the weaker one, and it is still worth having: count the updates that would violate the declared model as they go past, and report them. It cannot prevent the violation, it costs a counter, and it converts a silent scope error into a number somebody can look at. Nothing above suggests that number will be zero.

What the machinery does about it #

Three of the four have a mechanical answer and this phase implements it.

Every structure declares the models it is valid in. Every update sequence’s model is computed from the sequence rather than declared alongside it. And the runner refuses when the two do not match — twice, once for the structure and once for the data, and the second is the check that catches mistakes nobody made deliberately.

Where a figure wants to show what happens outside a model, it passes a flag that records the violation instead of throwing, and the plate prints it. A deliberate violation is a parameter here, and every figure that commits one says so.

This is the same device as the one-pass wrapper, which throws on a second iteration, and the table that refuses a cell read before it is written. In all three cases the model’s defining restriction is enforced by machinery rather than remembered by an author, and in all three cases the restriction is the one that is easiest to violate by accident because the violating code looks exactly like the correct code.

The table at three settings #

The table is the argument, and a table computed once from one set of structures at one deletion rate is the kind of thing this page exists to warn about.

The third reading drops the structures whose model is about deletions at all, which leaves the two whose dials are elsewhere.

Which of these the previous phase got wrong #

None of them, in the sense that no measurement it recorded is incorrect. Every number in that phase is a true measurement of a cash-register stream with ideal-enough hashing.

What it got wrong is the scope of its captions, and the correction is a sentence per plate rather than a re-measurement. “Count-Min’s estimate is never below the truth” is true in the model that phase worked in and false in a model a reader may well be in. “HyperLogLog is within 1.04/√m” assumes a hash family nobody there examined.

This phase’s rule — every plate names its model — is the repair, and it is applied to the new plates rather than retrofitted to the old ones, because the old plates are correct and the field’s index now carries the model in the same place the external-memory field carries its $B$ and $M$ and the coding field names its model.

The general form, which outlives this subject: a bound has a subject, and the subject is a set of assumptions about the input. A structure cannot check them. A caption cannot carry them. What can is a declaration, checked against the data, at the moment the two meet.