Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Additive error — where it appears

An error stated as a fixed quantity rather than a fraction — for a frequency sketch, a share of the whole stream, whatever the key's own count. Quoted as a share of the whole stream it flatters a summary asked about a rare key, whose own count may be smaller than the slack.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

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.

streaming · Sketch 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%

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.

wrong · Sketch key 05,416short by 4,163key 1462short by 4,154key 31short by 2,099key 71short by 943key 19401short by 3counter held (bar) against true count (tick)12 counters · 768 bits · no randomnessbound N/(k+1) = 4,615

The items that survive k counters

Misra-Gries keeps k counters, decrements all of them on a miss, and never returns a count above the truth — with no hashing, no randomness and no failure probability. At equal state it is more accurate than the randomised sketch on the question both are usually asked, at every size measured.

structures · Sketch Count-Min 4×64exact184 under16 overrms 42Count-Sketch 4×64-174-8708717499 under101 overrms 13general turnstile · insertions and deletions, counts may go negative · counts exact8,192 bits each

When the stream takes it back

Count-Min's estimate is never below the truth. That is a theorem about a stream where every update adds — and allow deletions that can take a count below zero and it comes back under on 93% of queries, with nothing in the number to say so.

wrong · Sketch Count-Min 4×64exact0 under200 overrms 303Count-Sketch 4×64-2,774-1,38701,3872,774120 under80 overrms 256cash register · insertions only, Zipf s = 1.1 · counts exact8,192 bits each

A sketch that is allowed to be under

Count-Min's estimate is never below the truth, and it pays for that with an error proportional to the whole stream. Give every key a sign and take a median instead, and the same table is 2.7 times more accurate on the keys anybody asks about — and wrong in both directions.

structures · Moment

Named alongside it

The objects these essays reach for when they reach for this one.

Count-Min sketchOne-sided errorEstimatorHeavy hitterSketchState bitsZipf distributionGuaranteeCount-SketchDeterministic algorithmFailure probabilityLinear sketch

All concepts