THE FOLD / GLITCH / HEISENBUG / THE BLOOM FILTER
THE BLOOM FILTER
probabilistic membership with one-sided error
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Bloom filter tests set membership using a bit array and k hash functions, in tiny memory — without storing the elements at all. To add an item, set the k bits its hashes point to; to query, check those k bits. If any is 0 the item is definitely absent; if all are 1 it is probably present. The only possible error is a false positive — never a false negative.
It is everywhere: databases, caches, spell-checkers, cryptocurrency clients.
LIT verified live: over 200 filters every inserted element queries positive (zero false negatives), so all error is one-sided; the false-positive rate is measured live against the ideal (1−e−kn/m)k (window.__bloomfilter). FIG honest: with simple double-hashing the measured FP runs a little above the ideal-independent-hash bound.
It is everywhere: databases, caches, spell-checkers, cryptocurrency clients.
LIT verified live: over 200 filters every inserted element queries positive (zero false negatives), so all error is one-sided; the false-positive rate is measured live against the ideal (1−e−kn/m)k (window.__bloomfilter). FIG honest: with simple double-hashing the measured FP runs a little above the ideal-independent-hash bound.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at heisenbug — a false positive is exactly that intermittent phantom: the filter says ‘maybe present’ for something that was never added, an error that only ever points one way. AVAN (AI) built the instrument: the bit array, the k hashes, the no-false-negative check, the live FP-rate measurement.
Credit as content: Burton Howard Bloom (1970). The weave: David names the heisenbug; I set k bits per item and show that a zero bit proves absence while the only mistakes are one-sided false positives.
Credit as content: Burton Howard Bloom (1970). The weave: David names the heisenbug; I set k bits per item and show that a zero bit proves absence while the only mistakes are one-sided false positives.
3 ONE DIMENSION
Adding an item sets the k bits its hashes select. A query passes only if all k are already 1 — so a single 0 among them is a certain ‘not in the set’.
4 TWO DIMENSIONS · INTERACTIVE
Insert items, then query members and non-members; members always pass, and the measured false-positive rate is shown against the ideal.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the bit pattern that can answer ‘definitely absent’ with certainty.
AVAN’s addition (the inverse-companion): you can answer ‘definitely NOT in the set’ with certainty while never storing the elements — k hash bits per item, and an unset bit proves absence; the only error is a false positive, never a false negative. The inverse of ‘keep the members to test them’ is ‘keep only bits, and let a zero bit prove non-membership.’ Magenta is the elements never stored; green is the bit pattern that can only err toward ‘maybe’. One-sided error, tiny memory.
LIT Genuine Bloom filter (Bloom 1970). Verified live: over 200 filters every inserted element queries positive (zero false negatives, error is strictly one-sided) (window.__bloomfilter.noFalseNegatives && .oneSidedError); the measured false-positive rate is reported.
FIG No framing on the guarantee: the no-false-negative / one-sided-error property is exact and verified. HONEST caveat: the interactive measures the false-positive rate against the ideal-independent-hash bound (1-e^-kn/m)^k, and with simple double-hashing the measured FP runs modestly (2-5x) above that ideal — a real property of double hashing, reported not hidden. Magenta is the elements never stored, green the bit pattern that only errs toward 'maybe'.
FIG No framing on the guarantee: the no-false-negative / one-sided-error property is exact and verified. HONEST caveat: the interactive measures the false-positive rate against the ideal-independent-hash bound (1-e^-kn/m)^k, and with simple double-hashing the measured FP runs modestly (2-5x) above that ideal — a real property of double hashing, reported not hidden. Magenta is the elements never stored, green the bit pattern that only errs toward 'maybe'.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HEISENBUG · David Lee Wise (ROOT0), with AVAN