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

Poisson — where it appears

The distribution of a count of independent events at a steady rate, with variance equal to its mean. It describes how many keys land in one block of a hashed filter and how many arrivals a steady stream brings in a second, and its tail sets how far above the mean a count strays.

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

10,000100,000keys in the filtershare of absent keys answered yes0.04%0.05%0.06%0.08%0.10%0.12%the emptier of twoone blockone block, Poisson averageone block, by threshold16 bits a key, 512-bit blocks2,000,000 absent queries a point

A penalty set by the block

A blocked Bloom filter pays a penalty for its uneven block loads, and a threshold that lets a lookup work out its block repays about a third of it — measured on 2,048 keys, with a prediction that larger filters would widen the gain. From 2,048 keys to 131,072 nothing moves: one block holds 0.085% to 0.090% against a computed 0.086%, and the threshold design 0.063% to 0.066%. The busiest block grows and the rate does not follow it. What sets both the penalty and the repair is the keys a block holds. A threshold turns out to be worth one doubling of the block's width, and nothing once a block holds 128 keys.

randomness · Randomness 0.00%0.05%0.10%0.15%256 bits · one block0.142%256 bits · a threshold on the first0.087%256 bits · thresholds on both0.096%512 bits · one block0.090%512 bits · a threshold on the first0.063%512 bits · thresholds on both0.065%1024 bits · one block0.063%1024 bits · a threshold on the first0.055%1024 bits · thresholds on both0.056%with no spreadwhat the spread adds16 bits a key, 8,192 keysno spread: every block at its mean load

The bits a second threshold costs

A blocked Bloom filter whose first block carries a threshold was proposed a second threshold on each key's second block, with a third block for keys both refuse. It does what it was meant to: at 512-bit blocks it removes nearly a third of the load spread the first threshold left. And the rate does not move — 0.065% against 0.063% — because the second table, paid for in blocks, raises the rate the filter would have with no spread at all by as much as the narrower spread saves. The threshold was stored in more bits than it needs: at four bits, one threshold beats the eight-bit design by 9%, and a second threshold of the best width buys nothing beyond the noise.

randomness · Randomness

Named alongside it

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

Balls in binsBlocked filterBloom filterDesign parameterFalse-positive rateLoad balancingMaximum loadThresholdTwo choicesCacheLocality

All concepts