THE FOLD / GLITCH / HEISENBUG / THE MAYBE
THE MAYBE
the Bloom filter — certain no, probable yes
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Bloom filter. You want to ask ‘have I seen this before?’ over millions of items, in a sliver of memory. A Bloom filter (Burton Bloom, 1970) is just a bit array and k hash functions. To insert an item, hash it k ways and set those k bits. To query, hash it k ways and check those bits.
The result is a beautiful lopsided honesty: if any of the k bits is 0, the item is definitely not in the set. If all k are 1, it is probably present — but maybe not, because other items could have set those same bits. False positives happen; false negatives never do. The false-positive rate is (1 − e−kn/m)k for n items in m bits.
LIT verified live: with m=4096 bits, k=6 hashes, n=400 items, this page confirms every inserted item still tests present (zero false negatives), and the measured false-positive rate on unseen items matches the formula to within 0.02 (window.__bloom.noFalseNegatives && fpMatches). FIG no framing: the bits, the k hashes, and the false-positive formula are exactly what the filter does.
The result is a beautiful lopsided honesty: if any of the k bits is 0, the item is definitely not in the set. If all k are 1, it is probably present — but maybe not, because other items could have set those same bits. False positives happen; false negatives never do. The false-positive rate is (1 − e−kn/m)k for n items in m bits.
LIT verified live: with m=4096 bits, k=6 hashes, n=400 items, this page confirms every inserted item still tests present (zero false negatives), and the measured false-positive rate on unseen items matches the formula to within 0.02 (window.__bloom.noFalseNegatives && fpMatches). FIG no framing: the bits, the k hashes, and the false-positive formula are exactly what the filter does.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in HEISENBUG, beside THE TURMITE ZOO — the glitch domain of the answer you can’t quite pin down. A Bloom filter’s ‘maybe’ is the friendliest Heisenbug there is: a firm no, or a hedged yes, never a lie in the other direction. AVAN (AI) built the instrument: the bit array, the k-hash insert, the false-positive measurement.
The weave: David names the seat (the certain-no, probable-yes); I make the bits light and the rate checkable — the array in 1D, live inserts and queries in 2D, the bit-ring probed in 3D. The sphere is the seam. Credit: Burton Howard Bloom (1970).
The weave: David names the seat (the certain-no, probable-yes); I make the bits light and the rate checkable — the array in 1D, live inserts and queries in 2D, the bit-ring probed in 3D. The sphere is the seam. Credit: Burton Howard Bloom (1970).
3 ONE DIMENSION
The bit array. Inserting an item lights the k bits its hashes point to. Over many items the array fills; a query is a lookup of k bits — one dark bit is a certain ‘no’, all lit is a ‘maybe’.
4 TWO DIMENSIONS · INTERACTIVE
Insert items and watch the grid fill. Query present always answers yes; query absent usually answers ‘definitely not’ but occasionally ‘maybe’ — a false positive. The measured false-positive rate tracks the formula as the filter loads.
5 THREE DIMENSIONS + AVAN’S INVERSE
The bit array wound into a turning ring — green where a bit is lit, dark where it is clear.
AVAN’s addition (the inverse-companion): the magenta marks are a query’s k probes. A perfect set answers both yes and no with certainty but costs memory for every element. The Bloom filter is its inverse trade: it keeps almost nothing, and in exchange it can prove absence but only suggest presence. Notice which way the asymmetry runs — a single dark probe is an unshakable no; all-lit is only a maybe, because the lit bits could belong to others. Certainty flows toward the negative. The green is what has been marked; the magenta is a question that can be firmly refused but never firmly granted — knowledge that is sure only about what is not there.
LIT Genuine Bloom filter (Burton Howard Bloom, 1970) with murmur-style hashes. Verified live: with m=4096 bits, k=6 hashes, n=400 items, every inserted item still tests present (zero false negatives), and the measured false-positive rate on unseen items matches the formula (1-e^(-kn/m))^k to within 0.02 (window.__bloom.noFalseNegatives && fpMatches, both true). The asymmetry — provable absence, only probable presence — is exact and structural.
FIG No metaphor is doing the work: the bit array, the k hashes, and the false-positive-rate formula are exactly the filter. The 'maybe' is literal — a positive query is genuinely uncertain, a negative query genuinely certain, and both are demonstrated in-page.
FIG No metaphor is doing the work: the bit array, the k hashes, and the false-positive-rate formula are exactly the filter. The 'maybe' is literal — a positive query is genuinely uncertain, a negative query genuinely certain, and both are demonstrated in-page.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HEISENBUG · David Lee Wise (ROOT0), with AVAN