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 7 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 11010010³0.00010.0010.010.1keys held, as a multiple of the forecast of 2,000share of absent keys answered yesthe 1% targetten bits reservedrebuilt from the storerebuilt only when it cannotgrowa stack of Bloom filtersforecast 2,000 at 1%, grown to 2,000,00020,000 absent keys a point

The day a filter cannot grow

A fingerprint table dies when its quotient reaches its shortest fingerprint, and a filter cannot lengthen a fingerprint because it does not keep its keys. The store it filters does. Rebuilt from that store whenever its own count says its rate has passed 1%, a table grown a thousandfold never exceeds 1.05% and ends holding exactly what a reserve of ten bits holds — 18.9 bits a key — having read the store 1.34 times over. The reserve paid its bits early: 34.8 a key at four times the forecast, where the rebuilt table held 18.4. Which one is cheaper depends on whether the growth arrives.

randomness · Randomness a second hash, unordered0.054 entries read on an absent key14.435.79 storedthe bits below the bucket, unordered0.059 entries read on an absent key14.435.79 storedthe bits below the bucket, sorted0.057 entries read on an absent key8.975.21 storedthe bucket's own bits, sorted5.743 entries read on an absent key11.275.80 storedtag comparisons an absent key's lookup makes8,192 slots · buckets of 8 · 8-bit tags38% fewer

A tag that answers more than yes

A byte of hash in front of each entry has one bit of output per slot: this tag matches or it does not. Cut it from an ordered field instead and a bucket's tags can be kept sorted, so a lookup stops at the first tag above its own — 8.97 comparisons for an absent key instead of 14.43, for 3.55 tag-byte shifts an insertion. The obvious ordered field is the trap. Take the tag from the bucket index's own bits and every key in a bucket shares them: 5.74 entry reads on an absent key instead of 0.054, a hundred and seven times more.

machine · Machine 501001500.2000.4000.6000.800load: keys held ÷ slotsbytes held per keythe entry, 32 bytesslotted entriespacked, a pointer a bucketpacked, groups of 4 bucketspacked, groups of 1616,384 slots, buckets of 8, 32-byte entrieslabels at the lowest load

Entries found by the rank of their tag

A bucket whose tags are kept sorted is an index: the position a tag is found at is its rank, and a rank can address an entry. Drop the fixed slots and pack each bucket's entries in tag order, and a cuckoo table of 32-byte records holds 36.1 bytes a key at half load where slots hold 66.1, and 34.3 against 36.7 at 0.9. Every insertion pays for it by moving the entries after its rank: 99 bytes against 36 at half load, 586 against 105 at 0.9. The prediction that packing would lose above 70% load was about the wrong quantity.

machine · Machine

Named alongside it

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

Design parameterFalse-positive rateBloom filterCuckoo hashingApproximate membershipCacheHonest limitLoad factorLocalityResizingSpace time tradeAmortisation

All concepts