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

Resizing — where it appears

Replacing a structure's storage with a larger allocation and moving its contents across once it fills. A hash table can resize because it keeps its keys, and a Bloom filter cannot, because its bits record positions that mean nothing in a table of another size.

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

110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends

What amortised means

Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws.

structures · Structure 0.01%0.1%1%10%100%1,0002,0003,0004,0005,0006,0007,0008,000keys insertedabsent keys answered yesone filterm = 19,171, k = 7; dotted: the design sizedashed: the design rate

A filter past its design size

A Bloom filter sized for two thousand keys at one per cent answers yes to 15.6% of absent keys at four thousand and 68.1% at eight thousand. Nothing fails and nothing warns. A stack of filters that adds a tighter layer whenever the top one fills holds 2.0% at eight thousand, under a bound it can state in advance — in 2.9 times the bits of one filter sized for eight thousand from the start.

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

Named alongside it

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

Bloom filterFalse-positive rateAmortisedError budgetFingerprintGrowth factorGuaranteeLoad factorOne-sided errorSpace overheadTrade offAmortisation

All concepts