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

Forecast — where it appears

The number of keys a structure is sized for when it is built, fixed before the keys arrive. A filter's rate, a table's slots and a reserve of bits are all set from it, and the question for any growing design is how far the forecast may be wrong.

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

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

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 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

Named alongside it

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

AmortisationApproximate membershipBloom filterDesign parameterFalse-positive rateFingerprintQuotient filterResizingSpace time tradeHash functionHonest limitThreshold

All concepts