Stable Bloom Filter

Membership testing over an unbounded stream in bounded memory: old entries fade out probabilistically so the false-positive rate stabilizes instead of growing forever like a Scalable Bloom Filter.

How it works

A Scalable Bloom Filter handles an unbounded stream by growing memory forever. A Stable Bloom Filter instead fixes its memory (m cells, each holding a small counter up to Max) and continuously evicts old information to make room for new items.

On every add(): first d randomly chosen cells are decremented by 1 (regardless of what item they belong to), then the k hash-derived cells for the new item are set to Max. Because eviction happens on every insert whether or not the filter is "full," the fraction of cells at Max converges to a steady state rather than climbing toward 1.

The cost: this filter can produce false negatives. An old item can eventually be evicted and reported as absent, something a classic or counting Bloom filter never does. Larger d means faster forgetting (lower memory pressure, shorter memory); smaller d means items stick around longer before fading.

Interactive demo

Cells (m)64
Hash fns (k)3
Evicted / insert (d)3
Fill ratio0.00
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new StableBloomFilter(m, k, d?, max?)Allocate m counter cells (0..max, default max=3) with k hash functions; d cells evicted per insert (default ~2% of m).O(m) space
add(item): voidDecrement d random cells, then set the k derived cells to max.O(k + d) time
has(item): booleanTrue if all k derived cells currently equal max.O(k) time
fillRatio(): numberFraction of cells currently at max, converging to a steady state under sustained inserts.O(m) time

References

Original papers

Library implementations

Real-world use cases