Algorithms & Data Structures
the bound is a claim, and it is checkable
What is taught wrongly

The guarantee that is one query wide

A sketch described as accurate to within a per cent is accurate to within a per cent of the whole stream, not of the number asked about. On a skewed stream the same sketch is 4% wrong about its heaviest key and 34,100% wrong about one of its rarest, and both figures satisfy the bound.
21 min read 7 figures A guarantee is not a resultThe answer is an estimateA limit is not a prediction

Accurate to within one per cent, with 99% confidence.

That sentence is four claims. Within one per cent of what. With 99% confidence of what event. Per query, or across all queries. And measured on which stream. Three of the four are usually dropped, and each of the three, dropped, turns the sentence into something that is not true of the structure it describes.

Relative error against a key's true count, 4×64 sketchOne mark per distinct key in a Zipf stream of 60,000 items. The horizontal position is how often that key really occurred; the vertical is how far above the truth the sketch's estimate is, as a fraction of the truth. The fall is almost exactly a slope of −1, because the sketch's error is a fixed number of counts — about 2,548 here, being e/w of the whole stream — divided by whatever the key's own count happens to be. The heaviest key is over by 4.11% and the rarest by 34100%: the same sketch, the same query, and a factor of 8,290 between them.1101001,0000.111010010³true count of the keyrelative errorheaviest keyrarest key4×64 counters · 8,192 bits · Zipf s = 1.1 · 3,528 distinct keys at 702 positions4.11% to 34100%
Fig. 1 One run of a Count-Min sketch, with every distinct key in the stream plotted by its true count against the relative error of its estimate. The fall is close to a slope of −1 for a reason that is the whole of this essay: the sketch’s error is a roughly fixed number of counts, and dividing a fixed number by the key’s own count gives a straight line on these axes. The heaviest key is over by 4.11% and the rarest by 34,100%. The same sketch, the same query, the same run.

Within one per cent of what

The bound is f^x≤fx+εN\hat f_x \le f_x + \varepsilon N. The ε\varepsilon multiplies NN, the length of the whole stream, and never fxf_x.

That is not fine print. It is the difference between a structure that is uniformly accurate and one that is accurate about exactly the keys that carry most of the data. On the stream here — sixty thousand items, 3,528 distinct keys, Zipf-shaped — the additive slack at w=64w = 64 is eN/w=2,548eN/w = 2{,}548 counts. For the key that occurred 9,579 times that is a possible 27% and a measured 4%. For one of the 836 keys that occurred exactly once, the same 2,548 counts is a possible 254,700%.

A relative-error guarantee is a completely different object, and no structure of a fixed size can offer one. To be within 1% of a key that occurred once, the sketch would have to distinguish a count of one from a count of two for every key in the universe, which is the exact hash map and the linear-space floor that the floor under a summary computes. The additive form is not laziness in the analysis; it is the only form available.

Absolute over-count against a key's true count, 4×64 sketchThe same run, drawn as the absolute over-count rather than the relative one. The dashed line is the additive bound e/w × N = 2,548, and nothing is above it. This is the plot the guarantee is about, and it is flat: the error a key suffers has nothing to do with how often that key occurred. Every claim of the form "accurate to within a per cent" is a claim about this axis divided by the other one.1101001,00010³true count of the keyover-counte/w × N = 2,548heaviest keyrarest key4×64 counters · 8,192 bits · Zipf s = 1.1 · 3,528 distinct keys at 1,085 positionsbound 2,548, worst 1,363
Fig. 2 The same run, drawn as the absolute over-count. This is what the guarantee is about, and it is flat: the error a key suffers has essentially nothing to do with that key. The dashed line is eN/weN/w and nothing is above it. Everything alarming about the previous figure is this figure divided by the horizontal axis, and neither figure is more true than the other — they are the numerator and the ratio of the same measurement.

With 99% confidence of what event

δ\delta is the probability that one query exceeds the additive bound. It is not the probability that the sketch is correct, and it is not a property of the sketch at all — it is a property of a query against a sketch, and the events for different queries are not independent.

The practical form of the mistake is the one that shows up in monitoring systems. A design with δ=0.02\delta = 0.02 answering two hundred distinct queries is expected to breach on about four of them, and a system that alerts on any breach will alert. Nothing has gone wrong. The bound said one in fifty and there were two hundred.

Correcting for it is elementary — take δ′=δ/q\delta' = \delta/q for qq queries, which costs ln⁡q\ln q extra rows and is cheap because rows are logarithmic — and it is elementary only once somebody has noticed that the correction is needed. The bound as usually quoted contains no hint that the number of queries is a parameter.

The bound is loose, and by how much is not in the bound

Here is the measurement that makes the previous section awkward, and it is worth putting the two side by side rather than choosing one.

depth dd the design permits e−de^{-d} measured breach rate over 35,280 queries
1 36.8% 6.3%
2 13.5% 0.43%
3 5.0% 0.023%
4 1.8% 0

Every measured rate is well under what the design allows, and the ratio grows with depth: six times at d=1d = 1, thirty-one at d=2d = 2, two hundred and seventeen at d=3d = 3, and at d=4d = 4 not a single breach in thirty-five thousand queries against a permitted seven hundred.

So the per-query bound is honest and pessimistic, and the two failures — reading δ\delta as a per-sketch probability, and reading it as a description of how often the structure actually misses — pull in opposite directions and can cancel. A practitioner who read δ=0.02\delta = 0.02 as “the sketch is fine” and ran two hundred queries would probably have been right on this stream, for reasons that have nothing to do with the reasoning that got there.

This is the same shape as the constant the notation drops. The constant the notation drops is about a class that is right and a factor of three that decides everything; this is about a probability that is right and a factor of two hundred that decides whether the alarm fires. In both cases the missing quantity is a property of the input and the implementation, so no amount of staring at the bound recovers it and a measurement does.

Measured on which stream

Every number above is Zipf with exponent 1.1 over four thousand keys, and it is printed on every plate for the reason BB and MM are printed on every external-memory plate: change it and the numbers change.

The dependence is strong. On a uniform stream there are no heavy hitters at all, so the flat absolute error is a large relative error for every key at once and the sketch’s accuracy figures collapse across the board. On a more skewed stream the top key carries a larger share, the additive slack is a smaller fraction of it, and the same sketch looks better. A published accuracy figure with no stream attached is not a measurement of the structure.

A 4×64 Count-Min table after 60,000 itemsEach cell is a counter and each row has its own hash, so a key lands in exactly one cell per row — the four ringed cells are where key 0 went. The darker a cell, the larger its count. Key 0 truly occurred 9,579 times; its four cells hold 9,945, 9,896, 9,897, 10,030, and the estimate is the smallest of them, 9,896. Every cell is the key's count plus whatever else collided there, so every cell is an overestimate and the minimum is the least bad one. The whole table is 8,192 bits against 162,288 for an exact counter.hash rowh1h2h3h4h1 → cell 62: 9,945h2 → cell 29: 9,896h3 → cell 19: 9,897h4 → cell 36: 10,030key 0 occurred 9,579 times · the minimum of the four is 9,896 · over by 317the additive bound at this width is e/w × N = 2,5484×64 counters · 8,192 bits · Zipf s = 1.1exact would take 162,288 bits
Fig. 3 Where the numbers come from. Four rows of sixty-four counters after sixty thousand items, with one key’s four cells marked. Each cell holds that key’s count plus about fifty-five other keys’ counts, and reading down the four marked cells shows the spread the minimum is choosing between. The over-count of the estimate is the smallest of four independent piles of junk, and how big those piles are depends on how much junk the stream contains.

Three more sentences that are not true

“The sketch is 99% accurate.” Accuracy and confidence are different parameters bought at different rates — ε−2\varepsilon^{-2} against ln⁡(1/δ)\ln(1/\delta) — and collapsing them into one percentage loses which was being described. A structure could be 99% confident of an answer that is 400% wrong, and several designs in this field are.

“More data makes it more accurate.” It makes it less accurate, in the only sense the bound describes: the additive term is εN\varepsilon N and NN grows. A sketch of fixed size over a growing stream degrades, and the thing that stays constant is the error as a share of the stream. This is the opposite of the intuition carried over from sampling, where more data is unambiguously better, and it is the single most reliable way to catch a sketch that has been reasoned about as though it were a sample.

“It is accurate to within ε\varepsilon.” The bound says at most εN\varepsilon N with probability at least 1−δ1-\delta. The realised error on the stream at hand is a different number, usually much smaller, occasionally larger, and never reported by the bound. A structure is deployed on a realised error and specified on a bound, and the whole of this site’s method is the position that the two need separate measurements.

Narrowing the table sharpens both readings at once, and in opposite directions, which is the clearest statement of what the guarantee is denominated in.

Absolute over-count against a key's true count, 4×16 sketchThe same run, drawn as the absolute over-count rather than the relative one. The dashed line is the additive bound e/w × N = 10,194, and nothing is above it. This is the plot the guarantee is about, and it is flat: the error a key suffers has nothing to do with how often that key occurred. Every claim of the form "accurate to within a per cent" is a claim about this axis divided by the other one.1101001,00010⁴true count of the keyover-counte/w × N = 10,194heaviest keyrarest key4×16 counters · 2,048 bits · Zipf s = 1.1 · 3,528 distinct keys at 676 positionsbound 10,194, worst 6,577
Fig. 4 The same stream through a table a quarter as wide. The additive bound is now e/w×N=10,194e/w \times N = 10{,}194 rather than 2,548, nothing is above it, and the plot is still flat — the error a key suffers still has nothing to do with how often that key occurred.
Relative error against a key's true count, 4×16 sketchOne mark per distinct key in a Zipf stream of 60,000 items. The horizontal position is how often that key really occurred; the vertical is how far above the truth the sketch's estimate is, as a fraction of the truth. The fall is almost exactly a slope of −1, because the sketch's error is a fixed number of counts — about 10,194 here, being e/w of the whole stream — divided by whatever the key's own count happens to be. The heaviest key is over by 21.83% and the rarest by 242500%: the same sketch, the same query, and a factor of 11,109 between them.1101001,00011010010³true count of the keyrelative errorheaviest keyrarest key4×16 counters · 2,048 bits · Zipf s = 1.1 · 3,528 distinct keys at 496 positions21.83% to 242500%
Fig. 5 And the same run read as a fraction of the truth. The heaviest key is now over by 21.83% rather than 0.00%, and the rarest by 242,500%. Four times fewer counters is four times the additive error and, on the key everybody actually queries, the difference between a number worth reporting and one that is not.

The interval nobody quotes

There is a construction that repairs a good deal of this and it costs almost nothing, which makes its absence from the usual account worth noticing.

Count-Min never goes below the truth. Misra-Gries never goes above it. Running both, at half the state each, gives an interval that provably contains the true count — not with probability 1−δ1-\delta, but certainly, because both one-sidednesses are unconditional.

32 Misra-Gries counters after 60,000 itemsThe bars are what the 32 counters held when the stream stopped; the tick beyond each marks that key's true count. Every counter is at or below the truth — the decrement rule can only take away — and the largest shortfall here is 1,397 against a guaranteed bound of N/(k+1) = 1,818. 12 of the 32 keys kept are among the 32 genuinely most frequent. No hashing and no randomness are involved anywhere: the bound holds on every stream, not on most of them.key 08,182short by 1,397key 13,219short by 1,397key 21,545short by 1,396key 3703short by 1,397key 4178short by 1,397key 546short by 1,393key 73short by 941key 82short by 857key 131short by 518key 191short by 355key 211short by 315key 231short by 311key 331short by 202key 381short by 172key 511short by 143key 621short by 118key 631short by 86key 941short by 62key 1251short by 43key 1411short by 43key 3291short by 20key 4361short by 10key 16461short by 4key 17491short by 2key 17501short by 1key 19401short by 3key 24281short by 4key 31371short by 1key 31651short by 0counter held (bar) against true count (tick)32 counters · 2,048 bits · no randomnessbound N/(k+1) = 1,818
Fig. 6 The other half of the interval. Thirty-two counters, no hashing, no randomness, and every bar at or below the truth by construction. Set beside the sketch’s estimate for the same key, the pair brackets the answer — and where the bracket is wide, that width is itself the useful output, because it is a statement about how much the summary does not know rather than a number that conceals it.

The width of that interval is the honest error bar, it is computed from the data rather than from the parameters, and it is different for every key. For the heaviest key in this stream it is a few hundred counts on nearly ten thousand; for a key that occurred once it runs from zero to two and a half thousand, which is the structure saying, correctly, that it knows nothing.

A single number with a footnote is what gets quoted instead. The reason is not mysterious — one number is easier to put in an interface than two — and the cost is that the interface cannot distinguish “about nine thousand five hundred” from “somewhere between nought and two thousand five hundred”, which are the two things the sketch actually said.

What a bound is for

None of this makes the bounds wrong or useless, and it would be a poor conclusion to draw. A bound does a job no measurement can do: it holds for streams nobody has run, including adversarial ones, and it is what lets a structure be sized before the data exists.

What a bound cannot do is tell anybody what a particular deployment will see, and the gap between the two is not a small correction. Two hundred and seventeen times, at d=3d = 3, on an ordinary stream. That is the size of the thing the bound is silent about, and it is the reason both numbers belong on the page.

Why this belongs in this field rather than beside the structure

The field of essays about what is taught wrongly has a consistent shape: a statement that is true, repeated in a form that has lost the conditions under which it is true. “Bubble sort is linear on nearly sorted data” is not what the counts say. “Quicksort sorts in place” covers three behaviours differing by a factor of n. “Hash lookup is O(1)” is a statement about an average over a family of hash functions and is not a statement about a run.

The sketch guarantee is the same shape and is worse in one specific way: the conditions are not merely omitted, they are encoded in a symbol that looks like it means something else. Reading εN\varepsilon N as “ε\varepsilon relative accuracy” is not carelessness about a caveat, it is a misreading of a formula that is right there. And the misreading is stable — it produces a mental model in which the structure is uniformly accurate, which is consistent with all the demonstrations anybody runs, because the keys anybody demonstrates on are the heavy ones.

Relative error against a key's true count, 4×128 sketchOne mark per distinct key in a Zipf stream of 200,000 items. The horizontal position is how often that key really occurred; the vertical is how far above the truth the sketch's estimate is, as a fraction of the truth. The fall is almost exactly a slope of −1, because the sketch's error is a fixed number of counts — about 4,247 here, being e/w of the whole stream — divided by whatever the key's own count happens to be. The heaviest key is over by 2.72% and the rarest by 67100%: the same sketch, the same query, and a factor of 24,649 between them.1101001,00010,0000.111010010³true count of the keyrelative errorheaviest keyrarest key4×128 counters · 16,384 bits · Zipf s = 1.1 · 23,925 distinct keys at 939 positions2.72% to 67100%
Fig. 7 The same measurement on a longer stream over a much larger universe, with a wider table. The picture is unchanged in shape and the numbers have all moved: the additive slack is larger because the stream is longer, the heavy keys are relatively heavier, and the tail is longer. What is invariant is the slope — a fixed absolute error divided by the key’s own count — and it is the invariant rather than any of the numbers that a reader of a sketch’s specification needs to carry away.

What to ask instead

The useful question is not how accurate a sketch is. It is: what fraction of the stream is the smallest thing worth being right about?

That has a direct answer. If the smallest interesting key carries a share ϕ\phi of the stream, and the estimate should be within a relative ρ\rho of it, then ε\varepsilon must be at most ρϕ\rho\phi and the width follows as w=e/(ρϕ)w = e/(\rho\phi). To be within 10% on keys carrying 1% of the stream takes w=2,719w = 2{,}719 columns — 43 kilobytes at four rows and 32-bit counters — and to be within 10% on keys carrying a tenth of a per cent takes ten times that.

Asked that way the trade is visible and the sizing is arithmetic. Asked as “how accurate is a Count-Min sketch”, it has no answer, and the answers people give are measurements of their own test data.

The same reframing works on the confidence half. Not “how confident should the sketch be” but: how many queries will be asked, and what happens when one of them is wrong? A hundred queries feeding a dashboard a human reads can tolerate a breach a week; a hundred queries feeding an automatic action cannot, and the correction is ln⁡q\ln q extra rows, which is three. Both numbers are cheap once somebody has asked for them and neither is recoverable from a structure that was sized by copying the parameters out of a paper.

Which keys get worse as the stream grows

“More data makes it less accurate” is true in the sense the bound describes and it is worth sharpening, because the sharpened version explains why sketches are nonetheless deployed on streams that run for years.

The additive slack is εN\varepsilon N and it grows with the stream. Whether that matters to a particular key depends on how that key grows.

A key whose share of the stream is stable — a popular endpoint that is always about 2% of traffic — has fx=0.02Nf_x = 0.02N, and the relative error is εN/0.02N=50ε\varepsilon N / 0.02N = 50\varepsilon. The NN cancels. Such a key is answered exactly as well after a year as after an hour, and no amount of stream makes it worse.

A key whose absolute count is fixed — something that happened four times last Tuesday and never again — has a relative error of εN/4\varepsilon N / 4, which grows without limit as the stream runs.

So the degradation is real and it is entirely confined to the second kind of key. That is a much more useful statement than the unqualified one, and it has a direct operational reading: a sketch over a growing stream is a structure whose accuracy about proportions is permanent and whose accuracy about rare absolute counts decays. A monitoring system asking “what share of requests hit this endpoint” is in the first case and needs no rotation; one asking “how many times did this error occur” is in the second and needs the sketch reset on a schedule, with the period set by how small an absolute count still has to be resolved.

It also explains the shape of the hero figure without any appeal to the bound. The keys on the left of it are the fixed-absolute-count keys, whose relative error is enormous and would grow; the keys on the right are the share-stable ones, whose relative error is small and would stay.

And the union bound assumes the queries were chosen first

The correction δ′=δ/q\delta' = \delta/q is right when the qq queries are fixed in advance. A great many real query sets are not, and the way they are chosen is the worst possible one.

The commonest use of a frequency sketch is to find the heavy keys and then report their counts. The keys asked about are therefore the keys the sketch itself estimated highest — which is to say, the keys where its error happened to be largest. That is not a sample of qq arbitrary queries; it is a sample deliberately enriched for the sketch’s own over-estimates, and the union bound has nothing to say about it because the queries depend on the same randomness the bound is over.

The effect has a direction and it is the unhelpful one. Count-Min never under-estimates, so selecting the top of its estimates selects keys whose piles of collision junk are unusually large, and the reported counts for exactly those keys are biased high by more than a randomly chosen key’s would be. The selection is doing the adversary’s work.

The standard repair is a second pass or a second structure: use the sketch to nominate candidates and something exact to count them, which is what a two-stage heavy-hitter pipeline does and why it exists. The repair is cheap because the candidate set is small. What is not available is a bound on the nominated keys’ estimates from the sketch alone, and a system that reports the sketch’s own numbers for the keys the sketch chose has used one structure for two jobs that need different guarantees.

What survives

Two sentences about a sketch are true without qualification and are worth separating from everything above, because the rest of this essay could be read as a case against the structures and is not.

The estimate is never below the truth. No probability, no stream dependence, no fine print — the property earned in a count that is never under, and the one that makes the number usable for anything at all.

The state does not grow. Eight kilobytes summarises a stream of any length over a universe of any size, and every alternative that is uniformly accurate is provably linear in something. Those two facts are what the structure is for. Everything else it is described as offering has conditions on it, and the conditions are in the formula rather than in a footnote.

It is worth saying why this essay exists at all, given that nothing in it is a correction to the literature. Every statement here is in the original papers, stated correctly, usually in the first page. What is being corrected is the transmission — the version that survives being repeated, in documentation, in blog posts, in the sentence a colleague says while recommending a structure. That version keeps the reassuring half of every clause and drops the qualifying half, and it does so consistently enough that the resulting mental model is predictable: uniformly accurate, confident overall, better with more data. All three are the reverse of the truth, and each of the three is one dropped phrase away from the paper.

Where this goes next

hash rowh1h2h3h4h1 → cell 30: 10,433h2 → cell 29: 10,624h3 → cell 19: 10,575h4 → cell 4: 10,895key 0 occurred 9,579 times · the minimum of the four is 10,433 · over by 854the additive bound at this width is e/w × N = 5,0974×32 counters · 4,096 bits · Zipf s = 1.1exact would take 162,288 bits A count that is never under The Count-Min sketch holds four rows of counters and answers how often a key occurred. Its error is one-sided with no probability attached — the estimate is never below the truth on any stream — and the probabilistic half of its guarantee is only about how far above. 10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly What O-notation does not say Big-O is a statement about a limit. It does not say how fast, it does not say which is better, it does not say anything at all about any particular n, and it discards precisely the factor that usually decides the answer. Knowing exactly what it claims is the difference between using it and being misled by it. 46810120.010.1bits per element (m / n)false-positive ratemeasured(1 − e^(−kn/m))^kfrom the bits set60,000 absent-key queries per point, seed 80800 false negatives at every size The formula everybody sizes filters with Fill a Bloom filter with four thousand random keys and its measured false-positive rate is within 4% of the textbook formula. Fill the same filter with the integers 1 to 4,000 and the rate is 30% worse than the formula says — not because the hash is bad, but because it is too good on that input.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

The 8 essays that link to this one and share the most of its objects, of 12 that link here.

The objects this essay names

Each one links to every other essay that touches it.

Additive errorCount-Min sketchEstimatorFailure probabilityGuaranteeHeavy hitterIndependence assumptionMedian of meansOne-sided errorRelative errorSketchState bitsZipf distribution