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

Fingerprint — where it appears

A short hash of a key, a few bits long, kept in place of the key itself. Two keys with equal fingerprints cannot be told apart, so a structure built on them answers membership with a false-positive rate set by the fingerprint's length and the number stored.

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

bits used · answers that were wrongBloom, bits cleared16,384 bits638 said no wrongly · 14 said yes wronglycounting, 4 bits a cell65,536 bits0 said no wrongly · 42 said yes wronglyfingerprints in two slots32,768 bits0 said no wrongly · 153 said yes wronglyand the condition on the caller1,000 deletions of keys never inserted lost 15 that were2,000 keys, 1,000 deleted, 20,000 absent keys querieda false negative is a different kind of wrong from a false positive

The evidence a filter cannot remove

A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.

randomness · Randomness 0.01%0.1%1%10%100%1,0003,0005,0007,0009,00011,00013,00015,000keys insertedabsent keys answered yesone Bloom filtera stack of Bloom filtersfingerprints, none reservedfingerprints, 3 reservedforecast 2,000, target 1.0%; dotted: the forecastdashed: the target rate

A filter that grows by moving a bit

A table of fingerprints can double in place, moving one stored bit of every fingerprint into its slot number, and so grow as one structure with one lookup where a stack of Bloom filters adds layers. Its false-positive rate is fixed by the fingerprint's length and not by the table, so with nothing reserved it doubles as the keys double — 0.69% at a forecast of 2,000, 5.7% at eight times that. Reserve three bits at the start and it holds 0.66% at eight times, in 294,912 bits, exactly what a table built for sixteen thousand keys would hold and fewer than the stack's 428,938. The reserve is a forecast of growth, and past it the rate climbs again.

randomness · Randomness 0.01%0.1%1%10%100%4,00012,00020,00028,00036,00044,00052,00060,000keys insertedabsent keys answered yesfingerprints, none reserved1 bit longer a doubling2 bits longer a doublingfingerprints, 5 reservedforecast 2,000, target 1.0%; dotted: the forecastdashed: the target rate

The bits given to the wrong keys

A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.

randomness · Randomness 48163264128110entry width, bytescache lines a lookup readsentries inlinea line of tags in front8,192 slots, load 0.9, buckets of 8keys the table holds

A lookup that stops caring how wide an entry is

Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.

machine · Machine

Named alongside it

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

False-positive rateBloom filterApproximate membershipCuckoo hashingDesign parameterGuaranteeOne-sided errorResizingSpace time tradeAlignmentAmortisationAmortised

All concepts