Variants and Extensions of Bloom Filters

Overview

The base Bloom filter trades certainty for compactness: no false negatives, a tunable false-positive rate, and a fixed bit array sized for a fixed n. Each variant below relaxes exactly one of those constraints — deletion, frequency estimation, unbounded growth, or space/latency — and each relaxation costs something back. The two variants that most often get confused, counting Bloom filters and cuckoo filters, both support deletion, which is precisely why picking between them needs more than "delete support: yes/yes". That head-to-head gets a dedicated section with a comparison table and a decision checklist near the end, after all five variants are on the table.

1. Counting Bloom Filters

A counting Bloom filter replaces each of the m single bits with a small saturating counter (commonly 4 bits, capped at 15). Insert increments the counters at the k hash positions; delete decrements them; a query reports "present" only if every one of the k counters is non-zero. The failure mode a plain Bloom filter can never have shows up here: deleting an item that was never inserted, or deleting the same item twice, can drive a counter shared with another item down to zero prematurely and produce a false negative for something that is still actually present.

Worked example (m = 10 slots, k = 3 hashes)

Suppose cat hashes to slots {2, 5, 8} and dog hashes to slots {5, 7, 9} — the two items collide at slot 5.

After deleting cat, slot 5's counter drops from 2 to 1, not to 0 — because dog still holds a claim on it. Querying cat afterward checks {2, 5, 8}, finds a zero at slot 2, and correctly reports absent. Querying dog checks {5, 7, 9}, finds 1/1/1, and correctly reports present. The diagram below renders exactly this three-step sequence.

2. Compressed Bloom Filters

Compressed Bloom filters reduce the storage or transmission size of the underlying bit array using techniques such as arithmetic coding or Golomb coding. The motivating case is not local memory but the wire: when a filter has to be shipped between nodes (for example, a proxy advertising its cache contents to peers), a slightly larger, sparser bit array that compresses well can transmit in fewer bytes than a smaller, denser array that is already near-incompressible — even though the sparser array is "bigger" before compression. The trade-off is CPU: every insertion, query, and especially every transmission now pays an encode/decode cost, so this variant is a bandwidth-for-CPU trade, not a free win, and it only pays off when the filter genuinely needs to travel over a network repeatedly.

3. Spectral Bloom Filters

A Spectral Bloom Filter (SBF) answers a different question than membership: not "have I seen this item?" but "about how many times have I seen it?" Like a counting filter it uses an array of counters incremented at each of the k hash positions on insert, but the query reads the minimum of the k counters as the frequency estimate, rather than just checking for non-zero. Taking the minimum matters because hash collisions can only inflate a counter — multiple items pushing the same slot upward — never deflate it, so the smallest of the k readings sits closest to the true count. That is the same "trust the least-contaminated slot" idea that Count-Min Sketch later formalized and popularized. A refinement called minimal increase (or conservative update) only increments the counters that are currently at that minimum on insert, instead of incrementing all k unconditionally, which measurably reduces over-counting error on skewed frequency distributions — the kind seen in word-frequency counting or network traffic analysis, where a handful of items dominate the stream.

4. Scalable Bloom Filters

A plain Bloom filter is sized for a target n up front; once the actual item count exceeds that, the false-positive rate degrades unboundedly because every slot saturates. A Scalable Bloom Filter (Almeida et al., 2007) sidesteps this by never fixing n at all. It keeps a growing list of Bloom filter "slices": the first slice is sized for a small initial capacity and a target false-positive rate p0; once its fill ratio crosses a threshold, a new slice is appended with capacity multiplied by a growth factor s (commonly 2 or 4) and a tightened target false-positive rate p0 · r^i, where r is a tightening ratio (commonly 0.8–0.9) and i is the slice index. New inserts always go to the newest slice; a query is a logical OR across every slice that currently exists. Because the per-slice false-positive rates shrink geometrically, the compounded false-positive rate across an unbounded number of slices still converges to a fixed bound instead of diverging as the item count grows. The price: both space and query cost (one hash-and-lookup per slice) grow with the number of slices ever created, and a slice, once written, is never rewritten or compacted — this variant buys unbounded growth, not compactness.

5. Cuckoo Filters

A cuckoo filter stores a short fingerprint — a hash of the item truncated to, say, 8–16 bits — instead of setting bits, and places it into a bucketed hash table using partial-key cuckoo hashing. Each item gets two candidate buckets: i1 = hash(x) mod m, and i2 = i1 XOR hash(fingerprint) mod m. Because XOR is its own inverse, i1 can be recovered from i2 and the fingerprint alone (i1 = i2 XOR hash(fingerprint)) — the filter never needs to see the original item x again to relocate a fingerprint, only the fingerprint it already stores. Buckets typically hold 4 fingerprints; a lookup checks at most 2 buckets, which is 2 cache lines, regardless of the configured false-positive rate. On insert, if both candidate buckets are full, the filter evicts a fingerprint already sitting in one of them, recomputes that evicted fingerprint's other candidate bucket via the same XOR trick, and tries to place it there — repeating this "kick" up to a bounded number of times.

Two consequences fall out of this design, and they are exactly what the selection section below weighs against counting Bloom filters. First, because a bucket lookup is 2 fixed cache-line reads instead of k scattered probes, and a fingerprint is a handful of bits instead of a whole counter, cuckoo filters can beat a counting Bloom filter on both space and lookup latency once the target false-positive rate drops below roughly 3%. Second, because insertion depends on a kick chain terminating within its bound, a cuckoo filter has no unconditional insertion guarantee — at high load factor (typically above ~95% for 4-way buckets) an insert can fail outright and force an application-level resize, something a counting Bloom filter never does short of counter saturation. The worked example and diagram below make the kick mechanics concrete.

Worked example: relocating a fingerprint

Bucket 13 already holds fingerprints A, B, C, G and is full. A new item's fingerprint F also maps to i1 = 13. The filter picks an existing occupant to evict — say G, whose own hash is hash(G) = 3 — and computes G's alternate bucket the same way any lookup would: alt(G) = 13 XOR 3 = 14. Bucket 14 has room, so G moves there, and F takes the slot G vacated in bucket 13. Note F's own alternate bucket was never needed: i2 for F would have been 13 XOR hash(F)=6 = 11, but the freed slot in bucket 13 made that unnecessary. The reversibility check confirms the trick: from bucket 14, hash(G)=3 recovers G's other bucket as 14 XOR 3 = 13 — the original bucket — with no need to touch G's original key.

Choosing between cuckoo and counting Bloom filters

Both variants support deletion, so "does it support delete" is not the axis that should decide between them. The axes that actually matter are space at your target false-positive rate, whether every insert is guaranteed to succeed, whether filters can be merged after the fact, and lookup latency.

Decision checklist

• Filters get merged across shards or time windows without a full rebuild (for example, hourly filters ORed into a daily filter) — pick the counting Bloom filter; the cuckoo filter's lack of mergeability breaks this pattern outright.
• Target false-positive rate is under roughly 3% and the lowest bits-per-item matters, and an occasional insert failure can be handled by a resize — pick the cuckoo filter.
• Every write must be accepted synchronously with zero chance of an operation-level rejection (for example, inline dedup sitting on a write path where a rejected insert breaks correctness) — pick the counting Bloom filter; its only failure mode degrades gracefully into a tiny extra false-positive risk instead of an outright reject.
• Lookup latency is bound by cache-line locality more than by raw memory footprint — pick the cuckoo filter for its fixed 2-probe lookup.
• The dataset size is also unknown or growing without bound — that is an orthogonal problem. Layer a Scalable Bloom filter strategy (Section 4) underneath whichever of the two is chosen, rather than treating growth as a reason to prefer one over the other.

In short: counting Bloom filters stay the safer default when mergeability or an unconditional insert guarantee is load-bearing; cuckoo filters win once the false-positive budget is tight and the workload can tolerate the rare resize.

Sources

• B. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, 1970 — the original filter these variants extend.
• L. Fan, P. Cao, J. Almeida, A. Broder, "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol," 1998 — origin of the counting Bloom filter.
• M. Mitzenmacher, "Compressed Bloom Filters," IEEE/ACM Transactions on Networking, 2002.
• S. Cohen, Y. Matias, "Spectral Bloom Filters," SIGMOD, 2003.
• P. Almeida, C. Baquero, N. Preguiça, D. Hutchison, "Scalable Bloom Filters," Information Processing Letters, 2007.
• B. Fan, D. Andersen, M. Kaminsky, M. Mitzenmacher, "Cuckoo Filter: Practically Better Than Bloom," CoNEXT, 2014.