Bits per element: the floor, and what a Bloom filter needs

Bits per element: the floor, and what a Bloom filter needs

For each false-positive rate: the information-theoretic floor log₂(1/ε), which no structure answering approximate membership can get under, and the 1.4427× of it a Bloom filter needs at its optimal k. The overhead is the same factor at every rate — 1/ln 2, or 44% — so it is not something a better choice of parameters removes. It is the price of the particular construction, and it is why the cuckoo and quotient filters exist.

Drawn at 690 × 306, wide on the page. Everything above is what bits-against-floor returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

3 essays call bits-against-floor. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.