Scalable Bloom Filter (Almeida, Baquero, Preguica, Hutchison 2007)

What if you don't know how many items will be inserted? Basic Bloom requires n up front. Insert too many and FP rate explodes.

Scalable Bloom Filter solves this by chaining sub-filters: when the current sub-filter fills, allocate a new, bigger, tighter sub-filter and start inserting into that one. contains(x) checks every sub-filter.

The growth rule

• New sub-filter capacity: previous_capacity × s (typically s = 2).
• New sub-filter FP target: previous_target × r (typically r = 0.5).

Why tighten? The math

If every sub-filter targeted the same FP rate p, after K sub-filters the cumulative FP rate would be roughly:

cumulative_fp ≤ 1 - (1 - p)^K  ≈  K * p

— it grows linearly in K. Bad.

With geometric tightening (r = 0.5):

cumulative_fp ≤ sum_{i>=0} p * r^i = p / (1 - r) = 2p

— bounded forever, no matter how many sub-filters you chain.

Lookup cost

CHECK iterates every sub-filter (each sub-filter is small enough that this is still fast). Modern implementations may parallelize the lookup across sub-filters.

Real systems

This pattern shows up in caching layers that grow unbounded (e.g. malware-sample dedup, large-scale crawler "seen URL" sets). Cassandra's row-cache Bloom and RocksDB's per-SSTable Blooms instead size each Bloom from a known item count, then RELY on the system's natural sharding to avoid needing scalability inside a single filter.