Counting Bloom Filters: Deletion with Counters

In one line

Clearing a bit on delete can erase another item's bit and create false negatives. A counting Bloom filter replaces each bit with a small counter (typically 4 bits): insert increments, delete decrements, and lookup checks counters are non-zero. It supports deletion at about 4× the memory.

0/6 · 0%

Think of it like this

A shared coat hook with a tally. Instead of one flag saying "a coat is here", each hook shows how many coats hang on it. When one person takes their coat, the tally drops by one but the hook still shows other coats.

Key ideas

01
Why plain deletes break: A and B both set bit 3. Deleting A clears bit 3; B now reads "definitely absent" even though it's present: a false negative.
02
Counting version: counter[i] += 1 on insert, −= 1 on delete; lookup checks all k counters > 0. B survives A's deletion because counter 3 goes from 2 to 1.
03
Counter width: 4 bits (max 15) is the classic choice; overflow probability is tiny for properly sized filters. On overflow, counters stick at max (never decremented) to avoid false negatives, at a slight cost.
04
Rules: only delete items that were actually inserted (deleting a never-inserted item that is a false positive decrements other items' counters → false negatives). Verify existence in the source of truth before deleting.
05
Costs: ~4× memory of a plain Bloom filter (100M at 1% ≈ 480 MB instead of 120 MB), more work per update, and the delete rule above.

Code & diagrams

counting.txttext

Plain Bloom:     insert A -> bits {3,7,9}; insert B -> bits {3,5,11}
                 delete A (clear 3,7,9) -> B's bit 3 is now 0 -> lookup(B) = ABSENT  (false negative!)

Counting Bloom:  insert A -> c[3]=1 c[7]=1 c[9]=1
                 insert B -> c[3]=2 c[5]=1 c[11]=1
                 delete A -> c[3]=1 c[7]=0 c[9]=0
                 lookup(B) -> c[3]=1 c[5]=1 c[11]=1 -> POSSIBLY PRESENT (correct)

CountingBloomFilter.javajava

public final class CountingBloomFilter<T> {
    private final byte[] nibbles;          // two 4-bit counters per byte
    private final long m; private final int k; private final Function<T, byte[]> enc;

    public void add(T item)    { for (long p : positions(item)) inc(p); }
    public void remove(T item) {           // caller must know the item was inserted
        if (!mightContain(item)) return;
        for (long p : positions(item)) dec(p);
    }
    public boolean mightContain(T item) {
        for (long p : positions(item)) if (get(p) == 0) return false;
        return true;
    }
    private int get(long p) { int b = nibbles[(int) (p >>> 1)] & 0xFF; return (p & 1) == 0 ? b & 0x0F : b >>> 4; }
    private void inc(long p) { int c = get(p); if (c < 15) set(p, c + 1); }          // saturate at 15
    private void dec(long p) { int c = get(p); if (c > 0 && c < 15) set(p, c - 1); } // never decrement a saturated counter
    // set(), positions(): same double hashing as the plain filter
}

Interview problem

The problem

Users can be added and removed

A membership check must support adding and removing users. Compare a plain Bloom filter, a Counting Bloom filter and a Cuckoo filter.

When it breaks

Deleting an item that was never inserted from a counting filter

What you see

If the item was a false positive, its k counters belong to other items; decrementing them can reach zero and create false negatives for real members.

Fix & prevent

Only delete items confirmed to exist in the source of truth (and inserted into the filter); never delete on a filter "maybe" alone.

Explain it without notes

Why do counting Bloom filters stop decrementing a saturated counter?

Practice

Compute memory for 50M items at 0.1% as a plain and a 4-bit counting Bloom filter.

Trade-offs

↔
Deletion costs about 4× memory with counting filters, or implementation complexity with cuckoo filters.

Done when you can

I can explain why plain deletes break and implement a counting Bloom filter safely.

Command Palette