THE FOLD / LOOT / THE HOARD / THE CUCKOO FILTER
THE CUCKOO FILTER
deletable membership with never a false negative
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The cuckoo filter answers “have I seen this item?” using tiny fingerprints in a compact table — like a Bloom filter, but it also supports deletion. Each item has two candidate buckets (the second reachable from the first by XOR-ing a hash of its fingerprint), so an item can be relocated cuckoo-style to make room. It can return a false positive (a fingerprint collision), but never a false negative: anything inserted and not deleted is always found.
LIT verified live: across 20 filled filters, every inserted item is found (no false negatives), and the false-positive rate on non-members is ~2% (window.__cuckoo). FIG no framing; the never-miss guarantee is exact, the FP rate is measured.
LIT verified live: across 20 filled filters, every inserted item is found (no false negatives), and the false-positive rate on non-members is ~2% (window.__cuckoo). FIG no framing; the never-miss guarantee is exact, the FP rate is measured.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-hoard — the vast collection you must ask “is this already in here?” without storing it all. The cuckoo filter is that membership oracle, deletions and all. AVAN (AI) built the instrument: the fingerprint, the two-bucket XOR addressing, the cuckoo eviction, and the no-false-negative check.
Credit as content: Fan, Andersen, Kaminsky & Mitzenmacher (2014). The weave: David names the hoard; I stash each item’s fingerprint in one of its two buckets (evicting when full), and confirm every stored item is always found while non-members only rarely collide.
Credit as content: Fan, Andersen, Kaminsky & Mitzenmacher (2014). The weave: David names the hoard; I stash each item’s fingerprint in one of its two buckets (evicting when full), and confirm every stored item is always found while non-members only rarely collide.
3 ONE DIMENSION
An item’s fingerprint goes in bucket i1 or i2 = i1 ⊕ hash(fingerprint). If both are full, kick an occupant to its alternate bucket — the “cuckoo” move — until everyone has a home.
4 TWO DIMENSIONS · INTERACTIVE
A cuckoo filter of fingerprints; query members (always found) and non-members (rarely a false positive), and delete items.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: membership from fingerprints in two buckets.
AVAN’s addition (the inverse-companion): test membership without storing the items — keep only short fingerprints, each in one of two XOR-linked buckets, relocating cuckoo-style when full, so the answer never misses a stored item (only rare false positives) and deletion works. The inverse of ‘store every item to answer membership’ is ‘store only fingerprints, two homes each — one-sided error, deletable.’ Magenta is the full item set you avoid storing; green is the fingerprint nest. Never a false negative.
LIT Genuine cuckoo filter (Fan, Andersen, Kaminsky & Mitzenmacher 2014). Verified live: across 20 filters each filled with ~700 items, every successfully inserted item is found — no false negatives — and the measured false-positive rate on non-members is around 2% (window.__cuckoo.noFalseNegatives; fpRate).
FIG No framing on the guarantee: the no-false-negative property is exact (every stored fingerprint is found in one of its two buckets); the false-positive rate is measured, not claimed exact. The fingerprint, two-bucket XOR addressing, cuckoo eviction, and no-false-negative check run in-browser. The AVAN inverse is honest — storing only short fingerprints in two XOR-linked buckets tests membership without the items, one-sided error and deletable; magenta is the full item set you avoid storing, green the fingerprint nest. Never a false negative.
FIG No framing on the guarantee: the no-false-negative property is exact (every stored fingerprint is found in one of its two buckets); the false-positive rate is measured, not claimed exact. The fingerprint, two-bucket XOR addressing, cuckoo eviction, and no-false-negative check run in-browser. The AVAN inverse is honest — storing only short fingerprints in two XOR-linked buckets tests membership without the items, one-sided error and deletable; magenta is the full item set you avoid storing, green the fingerprint nest. Never a false negative.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOARD · David Lee Wise (ROOT0), with AVAN