Bloom Filter Variants

In 1970, Burton H. Bloom described a data structure that could answer "have I seen this before?" using a handful of bits instead of storing the item itself. The idea is elegant: hash each element with $k$ independent hash functions and set the corresponding bits in a bit array of size $m$. To query, check all $k$ bits — if any is zero, the element is definitely absent; if all are one, it is probably present. The false-positive rate is approximately $(1 - e^{-kn/m})^{k}$, where $n$ is the number of elements inserted.

The catch is permanent: the classic Bloom filter cannot delete elements. Setting a bit for one element may share a bit with another, so clearing it would corrupt the filter for those other elements. For decades this was an accepted limitation — until engineers ran into systems where items expire, users unsubscribe, or cached entries are evicted.

Three main variants have emerged to fill that gap, each making a different bet on the space-speed-accuracy trade-off:

• Counting filter (Fan et al., 1998): replace each bit with a small counter. Insertions increment; deletions decrement. Simple, but counters consume 3–4× more space.
• Cuckoo filter (Fan et al., 2014): store compact fingerprints in a hash table that uses cuckoo hashing to displace items. Supports deletion natively and often outperforms Bloom filters at false-positive rates below 3%.
• Blocked Bloom filter (Putze et al., 2007): partition the bit array into fixed-size blocks that each fit in a single cache line. No deletion, but much faster in practice because every lookup touches exactly one cache line.

Each variant is a solved engineering problem with known closed-form bounds — the real question is which trade-off fits your workload. See also probabilistic data structures for the classic filter's foundation.

Below you can insert items into three filter variants side by side, then delete from the ones that support it, and finally query to see which returns a false positive.

<!-- {{c_demo_title}} -->
<div class="demo-wrap">
  <div class="controls">
    <label for="item-input">{{label_item}}</label>
    <div class="input-row">
      <input id="item-input" type="text" placeholder="{{placeholder_item}}" maxlength="20" />
      <button id="btn-insert" type="button">{{btn_insert}}</button>
    </div>
    <div id="msg" class="msg"></div>
  </div>
  <div class="filters-grid">
    <div class="filter-card" id="card-classic">
      <div class="filter-name">{{label_classic}}</div>
      <div class="filter-desc">{{desc_classic}}</div>
      <canvas class="bits-canvas" id="bits-classic" width="320" height="36" title="{{title_bits}}"></canvas>
      <div class="filter-actions">
        <button class="btn-del disabled" id="del-classic" type="button" disabled title="{{title_no_delete}}">{{btn_delete}}</button>
        <button class="btn-query" id="query-classic" type="button">{{btn_query}}</button>
      </div>
      <div class="result" id="result-classic"></div>
      <div class="stat" id="stat-classic"></div>
    </div>
    <div class="filter-card" id="card-counting">
      <div class="filter-name">{{label_counting}}</div>
      <div class="filter-desc">{{desc_counting}}</div>
      <canvas class="bits-canvas" id="bits-counting" width="320" height="36" title="{{title_counters}}"></canvas>
      <div class="filter-actions">
        <button class="btn-del" id="del-counting" type="button">{{btn_delete}}</button>
        <button class="btn-query" id="query-counting" type="button">{{btn_query}}</button>
      </div>
      <div class="result" id="result-counting"></div>
      <div class="stat" id="stat-counting"></div>
    </div>
    <div class="filter-card" id="card-cuckoo">
      <div class="filter-name">{{label_cuckoo}}</div>
      <div class="filter-desc">{{desc_cuckoo}}</div>
      <div class="cuckoo-buckets" id="buckets-cuckoo" title="{{title_fingerprints}}"></div>
      <div class="filter-actions">
        <button class="btn-del" id="del-cuckoo" type="button">{{btn_delete}}</button>
        <button class="btn-query" id="query-cuckoo" type="button">{{btn_query}}</button>
      </div>
      <div class="result" id="result-cuckoo"></div>
      <div class="stat" id="stat-cuckoo"></div>
    </div>
    <div class="filter-card" id="card-blocked">
      <div class="filter-name">{{label_blocked}}</div>
      <div class="filter-desc">{{desc_blocked}}</div>
      <canvas class="bits-canvas" id="bits-blocked" width="320" height="36" title="{{title_blocks}}"></canvas>
      <div class="filter-actions">
        <button class="btn-del disabled" id="del-blocked" type="button" disabled title="{{title_no_delete}}">{{btn_delete}}</button>
        <button class="btn-query" id="query-blocked" type="button">{{btn_query}}</button>
      </div>
      <div class="result" id="result-blocked"></div>
      <div class="stat" id="stat-blocked"></div>
    </div>
  </div>
  <div class="legend">
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
    <span class="legend-note">{{legend_note}}</span>
  </div>
</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; font-size: 14px; }
.demo-wrap { padding: .6rem .5rem; }
.controls { margin-bottom: .8rem; }
.controls label { font-weight: 600; display: block; margin-bottom: .3rem; }
.input-row { display: flex; gap: .4rem; margin-bottom: .35rem; }
#item-input { flex: 1; padding: .4rem .6rem; border: 1px solid #bbb; border-radius: 6px; font-size: 14px; }
.msg { font-size: .85rem; color: #666; min-height: 1.2em; }
.msg.err { color: #c92f3c; }
.filters-grid { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; }
@media (max-width: 500px) { .filters-grid { grid-template-columns: 1fr; } }
.filter-card { border: 1px solid #dde3ea; border-radius: 10px; padding: .6rem .7rem; background: #f9fafb; }
.filter-name { font-weight: 700; font-size: .92rem; margin-bottom: .15rem; }
.filter-desc { font-size: .76rem; color: #555; margin-bottom: .4rem; line-height: 1.4; }
.bits-canvas { display: block; width: 100%; height: 36px; border-radius: 4px; margin-bottom: .4rem; background: #e8eef3; }
.cuckoo-buckets { display: flex; flex-wrap: wrap; gap: 3px; margin-bottom: .4rem; min-height: 36px; align-content: flex-start; }
.bucket { width: 26px; height: 26px; border-radius: 4px; display: flex; align-items: center; justify-content: center; font: 600 9px ui-monospace, monospace; background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557; }
.bucket.used { background: #1d3557; color: #fff; border-color: #1d3557; }
.filter-actions { display: flex; gap: .35rem; margin-bottom: .35rem; }
button { font: 600 13px system-ui; padding: .35rem .7rem; border-radius: 6px; cursor: pointer; border: 1px solid #1d3557; }
.btn-del { background: #fff; color: #c92f3c; border-color: #c92f3c; }
.btn-del.disabled, .btn-del:disabled { opacity: .35; cursor: not-allowed; }
.btn-query { background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; font-size: 12px; padding: .25rem .6rem; }
.result { font-size: .82rem; font-weight: 600; min-height: 1.2em; margin-bottom: .2rem; }
.result.yes { color: #c97f0a; }
.result.no  { color: #0a7d33; }
.result.fp  { color: #c92f3c; }
.stat { font-size: .75rem; color: #666; }
.legend { margin-top: .7rem; display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; }
.legend-note { font-size: .78rem; color: #666; }

// Code not found

Notice what happens after a deletion: the counting filter and cuckoo filter correctly report the item absent, while the classic Bloom filter (shown for reference) still claims it might be present. The blocked filter also cannot delete — but it is the fastest to query because every lookup touches exactly one cache line.

All three variants solve the deletion problem — or the cache problem — but each pays a different price.

Counting filter replaces each bit with a $w$-bit counter (typically $w = 4$). Space grows by factor $w$, so a classic filter using $m$ bits becomes a counting filter using $wm$ bits. The false-positive rate stays the same formula, but now deletion is possible: to remove an element, decrement the $k$ counters. The one hazard is counter overflow: if more than $2^{w} - 1$ elements map to the same counter, the counter saturates and deletion becomes unsafe. In practice $w = 4$ (maximum 15 copies) is enough for most workloads.

Cuckoo filter takes a different route. It stores a short fingerprint $f$ of each element (typically 8–12 bits) in a compact hash table using two candidate buckets per fingerprint. Insertion uses cuckoo displacement: if both buckets are full, kick out a resident and relocate it. The key insight for deletion is that the fingerprint itself is the membership witness — removing it is safe. At false-positive rates below about 3%, a cuckoo filter uses less space than an equivalent Bloom filter, because fingerprints are shorter than the $k \log_2 e$ bits per element that a Bloom filter needs. The occupancy limit (typically 95%) is the main practical constraint.

Blocked Bloom filter does not add deletion at all. Instead it partitions the $m$-bit array into blocks of size $B$ (often 512 bits = one cache line). Each element is hashed to one block, and its $k$ sub-hash functions operate only within that block. The benefit is purely about hardware: a classic Bloom filter with $k = 10$ touches up to 10 scattered cache lines per lookup; a blocked filter touches exactly one. At the cost of a slightly higher false-positive rate for the same space, lookups are 2–4× faster on modern CPUs.

The headline comparison:

All four variants answer membership queries in $O(1)$ time. None can produce false negatives — if an element was inserted and not deleted, the filter will always say "probably yes." The differences live entirely in the constants: bits per element, cache misses per query, and whether the filter can forget.

Probabilistic membership filters appear wherever the alternative — storing the full set — is too expensive:

• Database LSM-trees (RocksDB, LevelDB, Cassandra): each SSTable carries a Bloom filter so reads can skip levels with certainty. RocksDB ships a blocked Bloom filter by default because the cache-line locality makes it faster on modern hardware, even though it cannot delete.
• CDN cache admission: caching every object seen once wastes storage on one-hit wonders. A cuckoo filter tracks which objects have been seen more than once — the second hit triggers caching, and the filter can delete entries as objects expire. Proposed and studied in the TinyLFU admission policy.
• DNS negative caching: a DNS resolver can use a counting filter to remember "this name does not exist," then decrement and eventually clear the entry when the negative TTL expires — something a plain Bloom filter cannot do.
• Network packet deduplication: routers use Bloom filters to detect duplicate packets at line rate. When the filter window slides, a counting filter can remove old entries rather than flushing the entire structure.
• Bioinformatics (k-mer counting): genome assemblers count short DNA substrings (k-mers). A counting filter naturally accumulates per-k-mer counts, and its delete operation removes low-frequency k-mers that are likely sequencing errors.

The pattern is always the same: pick the variant whose weaknesses you can tolerate. If you need deletes and have space, use a counting filter. If you need deletes and want space efficiency, use a cuckoo filter. If you never delete but need maximum throughput, use a blocked Bloom filter. For background on hashing and why false positives are unavoidable in sub-linear space, see the related articles.

The classic Bloom filter is one of the most space-efficient membership structures ever devised — but its inability to delete turned out to matter a great deal in practice. Three decades of follow-up work produced the counting filter (simple, costly), the cuckoo filter (space-efficient, deletable, slightly complex), and the blocked Bloom filter (fast, cache-friendly, but still immutable).

What all four structures share is the core guarantee: zero false negatives, a tunable false-positive rate, and $O(1)$ queries regardless of set size. The variants don't change the fundamental trade-off with the information-theoretic lower bound — you cannot represent $n$ elements in fewer than $n \log_2 e$ bits without some error. They simply move the error budget around in ways that fit different hardware and workload constraints.

Choosing among them is a textbook engineering decision: count your deletes, measure your cache-miss budget, and pick the filter whose weaknesses are the ones you can most afford to ignore.