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

Failure probability — where it appears

The chance that one query's answer misses its error bound, denoted δ, bought exponentially cheaply and specified per query rather than per structure. It is stated per query rather than per structure, so a table of a thousand answers is not covered by a bound written for one.

Named by 4 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 10,0000.1total bits of stateruns outside ±15%1 × 483 × 485 × 487 × 489 × 48240 runs per design · tolerance ±15% · truth 12,00067 → 3 failures

The estimate that is a median of means

An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.

randomness · 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 0%25%50%75%100%0.30.40.50.60.70.80.850.90.95keys per slotconstructions that failed2 hashes, 1 slot3 hashes, 1 slot2 hashes, 2 slots2 hashes, 4 slots20 constructions a point, 256 bucketsa lookup reads hashes × slots, whatever the keys

More hashes or wider buckets

A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.

randomness · Randomness

Named alongside it

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

EstimatorSketchState bitsAdditive errorCount-Min sketchGuaranteeHeavy hitterMedian of meansOne-sided errorRelative errorZipf distributionBottom-k

All concepts