hesela.devStable Bloom filter
A stable Bloom filter is an approximate stream-history filter that ages counter cells to bound memory while allowing both false positives and forgotten duplicates.
Queries test nonzero cells before selected cells are decremented and the arriving key's cells are reset to a maximum. Stable refers to limiting occupancy, not permanent membership or a guaranteed time-to-live. [1]
A negative answer can reject an earlier item. An aging filter therefore cannot directly replace a no-false-negative filter used to skip reads of authoritative data. [2]
Relations
- related
- bloom-filter, counting-bloom-filter, cuckoo-filter
Citations
- Deng and Rafiei. Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters. SIGMOD 2006. DOI: 10.1145/1142473.1142477.
- 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]