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

Count-Sketch — where it appears

A table of counters updated with a hashed sign and queried by a median, giving an unbiased two-sided estimate where Count-Min gives a one-sided bound. It gives an unbiased two-sided estimate where Count-Min gives a one-sided bound, and which is preferable depends on whether an overestimate is safe.

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

Also named here as linear sketch — the same set of essays touches all of them, so they are one junction rather than several.

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.

Additive errorCount-Min sketchLinear sketchOne-sided errorCancellationEstimatorFailure modeFrequency vectorGuaranteeHeavy hitterHonest limitMedian of means

All concepts