Scalable Bloom Filter

A Bloom filter that doesn't need to know its final size in advance: it grows by appending new, tighter slices as it fills up, keeping the compounded false-positive rate bounded instead of degrading.

How it works

A classic Bloom filter must be sized for an expected item count n up front; if more items arrive than planned, its false-positive rate quietly climbs past the target. A Scalable Bloom Filter avoids this by starting small and appending a new slice whenever the current slice reaches its capacity.

Each new slice targets a tighter false-positive rate than the last (multiplied by a ratio r, typically 0.9), so the series of per-slice rates p₀, p₀r, p₀r², ... forms a geometric sequence. The compounded false-positive rate across all slices converges to a bound of p₀ / (1 - r), no matter how many items arrive.

add() always writes to the newest slice only. has() must check every slice, since an item could have been inserted before the most recent growth event.

Interactive demo

This demo starts with a tiny 4-item slice so you can trigger growth quickly. Keep adding items and watch a new slice appear.

Slices1
Total items0
Current slice target p0.1000
Est. compounded FP rate0.0000
Slice 0: m=20, k=3, target p=0.1000, items=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 ScalableBloomFilter(n0, p0?, r?, growth?)Start with one slice sized for n0 items at false-positive rate p0 (default 0.1), tightening by r (default 0.9) per growth, growing capacity by growth× (default 2) each time.O(m) space per slice
add(item): voidGrows a new slice if the current one is at capacity, then sets k bits in the newest slice.O(k) time
has(item): booleanTrue if all k derived bits are set in any slice.O(k · slices) time
estimatedFalsePositiveRate(): numberCompounded false-positive estimate across all slices: 1 − ∏(1 − pᵢ).O(slices)

References

Original papers

Library implementations

Real-world use cases

  • Any Bloom-filter use case where the final item count is unknown ahead of time, e.g. deduplicating an open-ended crawl or event stream
  • Long-lived caches/filters that must keep a bounded false-positive rate as their working set keeps growing