Introduction

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 kk independent hash functions and set the corresponding bits in a bit array of size mm. To query, check all kk 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(1 - e^{-kn/m})^{k}, where nn 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.

Try It

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.

<!-- Bloom filter variants comparison demo -->
<div class="demo-wrap">
  <div class="controls">
    <label for="item-input">Item to insert / delete / query:</label>
    <div class="input-row">
      <input id="item-input" type="text" placeholder="e.g. alice" maxlength="20" />
      <button id="btn-insert" type="button">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">Classic Bloom</div>
      <div class="filter-desc">k=3 hash functions, m=32 bits. No delete.</div>
      <canvas class="bits-canvas" id="bits-classic" width="320" height="36" title="Bit array (dark = 1)"></canvas>
      <div class="filter-actions">
        <button class="btn-del disabled" id="del-classic" type="button" disabled title="This filter does not support deletion">Delete</button>
        <button class="btn-query" id="query-classic" type="button">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">Counting Filter</div>
      <div class="filter-desc">k=3 counters (4-bit each), m=32 slots. Delete supported.</div>
      <canvas class="bits-canvas" id="bits-counting" width="320" height="36" title="Counter array (dark = non-zero, number = count)"></canvas>
      <div class="filter-actions">
        <button class="btn-del" id="del-counting" type="button">Delete</button>
        <button class="btn-query" id="query-counting" type="button">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">Cuckoo Filter</div>
      <div class="filter-desc">8-bit fingerprints, 16 buckets × 4 slots. Delete supported.</div>
      <div class="cuckoo-buckets" id="buckets-cuckoo" title="Fingerprint slots (hex, red = queried fingerprint)"></div>
      <div class="filter-actions">
        <button class="btn-del" id="del-cuckoo" type="button">Delete</button>
        <button class="btn-query" id="query-cuckoo" type="button">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">Blocked Bloom</div>
      <div class="filter-desc">k=3 per block, 2 blocks of 16 bits. No delete, 1 cache line.</div>
      <canvas class="bits-canvas" id="bits-blocked" width="320" height="36" title="Blocked bit array (two cache-line blocks)"></canvas>
      <div class="filter-actions">
        <button class="btn-del disabled" id="del-blocked" type="button" disabled title="This filter does not support deletion">Delete</button>
        <button class="btn-query" id="query-blocked" type="button">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">Reset all</button>
    <span class="legend-note">Red = queried positions · Orange = probably present · Green = absent · Crimson = false positive</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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Universal-style hash with 32-bit mixing (no crypto needed).
function hashStr(str, seed) {
  let h = seed ^ 0xdeadbeef;
  for (let i = 0; i < str.length; i++) {
    h = Math.imul(h ^ str.charCodeAt(i), 0x9e3779b9);
    h ^= h >>> 16;
  }
  return (h >>> 0);
}
// 8-bit fingerprint for cuckoo filter (never zero so empty slot = 0 is safe).
function fingerprint(str) {
  return (hashStr(str, 0xabcdef01) & 0xff) || 1;
}

const M = 32;  // bit-array / counter-array size
const K = 3;   // number of hash functions
const BUCKETS = 16; // cuckoo table buckets
const SLOTS = 4;    // slots per bucket

// Filter state: all start empty.
let classicBits = new Uint8Array(M);
let countingArr = new Uint8Array(M);
let cuckooTable = Array.from({ length: BUCKETS }, () => Array(SLOTS).fill(0));
let blockedBits = new Uint8Array(M);
// Each block is half the array, corresponding to one cache line.
const BLOCK_SIZE = M / 2;

// Track what was actually inserted so we can label false positives.
const insertedSet = new Set();
const deletedFromCounting = new Set();
const deletedFromCuckoo = new Set();

let queryTarget = '';

function getHashes(item) {
  const h = [];
  for (let i = 0; i < K; i++) h.push(hashStr(item, i * 0x1234567 + 0xabcd) % M);
  return h;
}

function getBlockHashes(item) {
  // Map item to one of 2 blocks, then hash within that block.
  const block = hashStr(item, 0x99887766) % 2;
  const base = block * BLOCK_SIZE;
  const h = [];
  for (let i = 0; i < K; i++) h.push(base + hashStr(item, i * 0x1234 + 0xbeef) % BLOCK_SIZE);
  return h;
}

function insertClassic(item) {
  for (const b of getHashes(item)) classicBits[b] = 1;
}
function queryClassic(item) {
  return getHashes(item).every(b => classicBits[b]);
}

function insertCounting(item) {
  for (const b of getHashes(item)) if (countingArr[b] < 15) countingArr[b]++;
}
function deleteCounting(item) {
  // Safe decrement: never go below zero.
  for (const b of getHashes(item)) if (countingArr[b] > 0) countingArr[b]--;
}
function queryCounting(item) {
  return getHashes(item).every(b => countingArr[b] > 0);
}

function cuckooInsert(item) {
  const fp = fingerprint(item);
  const h1 = hashStr(item, 0x1111) % BUCKETS;
  const h2 = (h1 ^ hashStr(fp + '', 0x2222)) % BUCKETS;
  // Try both candidate buckets before kicking.
  for (const b of [h1, h2]) {
    for (let s = 0; s < SLOTS; s++) {
      if (!cuckooTable[b][s]) { cuckooTable[b][s] = fp; return true; }
    }
  }
  // Kick-and-relocate loop (max 20 rounds).
  let cur = h1; let curFp = fp;
  for (let i = 0; i < 20; i++) {
    const s = Math.floor(Math.random() * SLOTS);
    const evicted = cuckooTable[cur][s];
    cuckooTable[cur][s] = curFp;
    curFp = evicted;
    cur = (cur ^ hashStr(curFp + '', 0x2222)) % BUCKETS;
    for (let ss = 0; ss < SLOTS; ss++) {
      if (!cuckooTable[cur][ss]) { cuckooTable[cur][ss] = curFp; return true; }
    }
  }
  return false; // Table too full — in practice resize before this point.
}
function cuckooDelete(item) {
  const fp = fingerprint(item);
  const h1 = hashStr(item, 0x1111) % BUCKETS;
  const h2 = (h1 ^ hashStr(fp + '', 0x2222)) % BUCKETS;
  for (const b of [h1, h2]) {
    for (let s = 0; s < SLOTS; s++) {
      if (cuckooTable[b][s] === fp) { cuckooTable[b][s] = 0; return; }
    }
  }
}
function cuckooQuery(item) {
  const fp = fingerprint(item);
  const h1 = hashStr(item, 0x1111) % BUCKETS;
  const h2 = (h1 ^ hashStr(fp + '', 0x2222)) % BUCKETS;
  for (const b of [h1, h2]) {
    for (let s = 0; s < SLOTS; s++) if (cuckooTable[b][s] === fp) return true;
  }
  return false;
}

function insertBlocked(item) {
  for (const b of getBlockHashes(item)) blockedBits[b] = 1;
}
function queryBlocked(item) {
  return getBlockHashes(item).every(b => blockedBits[b]);
}

// Render a bit or counter array onto a canvas element.
function drawBits(canvasId, arr, highlightSet) {
  const canvas = document.getElementById(canvasId);
  if (!canvas) return;
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  const cellW = W / arr.length;
  for (let i = 0; i < arr.length; i++) {
    const lit = arr[i] > 0;
    const hi = highlightSet && highlightSet.has(i);
    ctx.fillStyle = hi ? '#e63946' : (lit ? '#1d3557' : '#d0d7df');
    ctx.fillRect(i * cellW + 1, 4, cellW - 2, H - 8);
    if (arr[i] > 1 && arr[i] < 10) {
      ctx.fillStyle = '#fff';
      ctx.font = 'bold 8px ui-monospace';
      ctx.textAlign = 'center';
      ctx.fillText(arr[i], i * cellW + cellW / 2, H / 2 + 3);
    }
  }
}

function drawCuckoo(highlightFp) {
  const container = document.getElementById('buckets-cuckoo');
  if (!container) return;
  container.innerHTML = '';
  for (let b = 0; b < BUCKETS; b++) {
    for (let s = 0; s < SLOTS; s++) {
      const fp = cuckooTable[b][s];
      const div = document.createElement('div');
      div.className = 'bucket' + (fp ? ' used' : '');
      if (fp) {
        div.textContent = fp.toString(16).padStart(2, '0').toUpperCase();
        if (highlightFp && fp === highlightFp) div.style.background = '#e63946';
      }
      container.appendChild(div);
    }
  }
}

function renderAll(queryItem) {
  const classicHi = queryItem ? new Set(getHashes(queryItem)) : null;
  const countingHi = queryItem ? new Set(getHashes(queryItem)) : null;
  const blockedHi = queryItem ? new Set(getBlockHashes(queryItem)) : null;
  const cuckooHi = queryItem ? fingerprint(queryItem) : null;
  drawBits('bits-classic', classicBits, classicHi);
  drawBits('bits-counting', countingArr, countingHi);
  drawCuckoo(cuckooHi);
  drawBits('bits-blocked', blockedBits, blockedHi);
}

function setResult(id, text, cls) {
  const el = document.getElementById(id);
  if (el) { el.textContent = text; el.className = 'result ' + cls; }
}
function setStat(id, text) {
  const el = document.getElementById(id);
  if (el) el.textContent = text;
}
function setMsg(text, isErr) {
  const el = document.getElementById('msg');
  if (el) { el.textContent = text; el.className = isErr ? 'msg err' : 'msg'; }
}

function countBits(arr) { return arr.reduce((a, b) => a + (b > 0 ? 1 : 0), 0); }
function countCuckooBuckets() {
  let n = 0; for (const row of cuckooTable) n += row.filter(x => x).length; return n;
}

function updateStats() {
  const filled = countBits(classicBits);
  setStat('stat-classic', i18nFmt('%n% / %m% bits set', { n: filled, m: M }));
  const cFilled = countBits(countingArr);
  setStat('stat-counting', i18nFmt('%n% / %m% counters non-zero', { n: cFilled, m: M }));
  const cuckooFilled = countCuckooBuckets();
  setStat('stat-cuckoo', i18nFmt('%n% / %t% fingerprint slots used', { n: cuckooFilled, t: BUCKETS * SLOTS }));
  const bFilled = countBits(blockedBits);
  setStat('stat-blocked', i18nFmt('%n% / %m% bits set', { n: bFilled, m: M }));
}

document.getElementById('btn-insert').addEventListener('click', () => {
  const val = document.getElementById('item-input').value.trim();
  if (!val) { setMsg('Please type an item first.', true); return; }
  if (insertedSet.has(val)) { setMsg(i18nFmt(''%item%' was already inserted.', { item: val }), true); return; }
  insertedSet.add(val);
  deletedFromCounting.delete(val);
  deletedFromCuckoo.delete(val);
  insertClassic(val);
  insertCounting(val);
  cuckooInsert(val);
  insertBlocked(val);
  setMsg(i18nFmt(''%item%' inserted into all four filters.', { item: val }), false);
  queryTarget = '';
  setResult('result-classic', '', '');
  setResult('result-counting', '', '');
  setResult('result-cuckoo', '', '');
  setResult('result-blocked', '', '');
  renderAll(null);
  updateStats();
});

document.getElementById('del-counting').addEventListener('click', () => {
  const val = document.getElementById('item-input').value.trim();
  if (!val) { setMsg('Please type an item first.', true); return; }
  if (!insertedSet.has(val) || deletedFromCounting.has(val)) {
    setMsg(i18nFmt(''%item%' was not inserted (or already deleted from this filter).', { item: val }), true); return;
  }
  deletedFromCounting.add(val);
  deleteCounting(val);
  setMsg(i18nFmt(''%item%' deleted from counting filter.', { item: val }), false);
  renderAll(null);
  updateStats();
});

document.getElementById('del-cuckoo').addEventListener('click', () => {
  const val = document.getElementById('item-input').value.trim();
  if (!val) { setMsg('Please type an item first.', true); return; }
  if (!insertedSet.has(val) || deletedFromCuckoo.has(val)) {
    setMsg(i18nFmt(''%item%' was not inserted (or already deleted from this filter).', { item: val }), true); return;
  }
  deletedFromCuckoo.add(val);
  cuckooDelete(val);
  setMsg(i18nFmt(''%item%' deleted from cuckoo filter.', { item: val }), false);
  renderAll(null);
  updateStats();
});

function doQuery(filterId) {
  const val = document.getElementById('item-input').value.trim();
  if (!val) { setMsg('Please type an item first.', true); return; }
  queryTarget = val;
  renderAll(val);
  const wasInserted = insertedSet.has(val);
  if (filterId === 'classic') {
    const found = queryClassic(val);
    if (!wasInserted && found) setResult('result-classic', 'FALSE POSITIVE — not inserted but filter says yes!', 'fp');
    else if (found) setResult('result-classic', 'Probably present', 'yes');
    else setResult('result-classic', 'Definitely absent', 'no');
  } else if (filterId === 'counting') {
    const found = queryCounting(val);
    const deleted = deletedFromCounting.has(val);
    if (!wasInserted && found) setResult('result-counting', 'FALSE POSITIVE — not inserted but filter says yes!', 'fp');
    else if (wasInserted && deleted && !found) setResult('result-counting', 'Absent (correctly deleted)', 'no');
    else if (found) setResult('result-counting', 'Probably present', 'yes');
    else setResult('result-counting', 'Definitely absent', 'no');
  } else if (filterId === 'cuckoo') {
    const found = cuckooQuery(val);
    const deleted = deletedFromCuckoo.has(val);
    if (!wasInserted && found) setResult('result-cuckoo', 'FALSE POSITIVE — not inserted but filter says yes!', 'fp');
    else if (wasInserted && deleted && !found) setResult('result-cuckoo', 'Absent (correctly deleted)', 'no');
    else if (found) setResult('result-cuckoo', 'Probably present', 'yes');
    else setResult('result-cuckoo', 'Definitely absent', 'no');
  } else if (filterId === 'blocked') {
    const found = queryBlocked(val);
    if (!wasInserted && found) setResult('result-blocked', 'FALSE POSITIVE — not inserted but filter says yes!', 'fp');
    else if (found) setResult('result-blocked', 'Probably present', 'yes');
    else setResult('result-blocked', 'Definitely absent', 'no');
  }
}

document.getElementById('query-classic').addEventListener('click', () => doQuery('classic'));
document.getElementById('query-counting').addEventListener('click', () => doQuery('counting'));
document.getElementById('query-cuckoo').addEventListener('click', () => doQuery('cuckoo'));
document.getElementById('query-blocked').addEventListener('click', () => doQuery('blocked'));

document.getElementById('btn-reset').addEventListener('click', () => {
  classicBits = new Uint8Array(M);
  countingArr = new Uint8Array(M);
  cuckooTable = Array.from({ length: BUCKETS }, () => Array(SLOTS).fill(0));
  blockedBits = new Uint8Array(M);
  insertedSet.clear();
  deletedFromCounting.clear();
  deletedFromCuckoo.clear();
  queryTarget = '';
  ['result-classic','result-counting','result-cuckoo','result-blocked'].forEach(id => setResult(id,'',''));
  ['stat-classic','stat-counting','stat-cuckoo','stat-blocked'].forEach(id => setStat(id,''));
  setMsg('All filters reset.', false);
  renderAll(null);
});

renderAll(null);
updateStats();
Result
Console

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.

The Real Trade-offs

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

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

Cuckoo filter takes a different route. It stores a short fingerprint ff 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 klog⁡2ek \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 mm-bit array into blocks of size BB (often 512 bits = one cache line). Each element is hashed to one block, and its kk sub-hash functions operate only within that block. The benefit is purely about hardware: a classic Bloom filter with k=10k = 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:

Variant Space vs classic Supports delete Cache lines per lookup
Classic Bloom 1× No Up to kk
Counting filter ww× (≈ 4×) Yes Up to kk
Cuckoo filter < 1× at low FPR Yes 2
Blocked Bloom 1× No 1

All four variants answer membership queries in O(1)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.

Where It Matters

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.

Conclusion

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)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 nn elements in fewer than nlog⁡2en \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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bloom-filter-variants/Content licensed under CC BY-NC 4.0.