hesela.devCounting Bloom filter
A counting Bloom filter tracks approximate set membership with counters that support insertions and deletions through matched increments and decrements.
Correct deletion requires an outstanding insertion, not merely a positive lookup. Exact counters preserve colliding live keys, but clipping overflow loses multiplicity and can later yield false negatives. [1]
Counter width and overflow policy are part of the contract. Keeping a saturated cell positive until rebuilding avoids decrementing an unknown count, at the cost of extra positives. These policies are distinct from intentional history decay. [2]
Relations
- related
- bloom-filter, stable-bloom-filter, cuckoo-filter
Citations
- Fan, Cao, Almeida and Broder. Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. ToN 8(3), 2000. DOI: 10.1109/90.851975.
- Hesela. Filter retention and counting: fixed-address counterexamples.
Sources & caveats
- The linked examples use explicit addresses and decay schedules; they do not estimate production error rates. [2]