20.3 What is a counting Bloom filter?

At the door: Instead of ticks, the bouncer keeps little tallies in each box. A guest arriving adds one to each of their three boxes; when they leave, the bouncer rubs one out of each. A box shared by two guests goes from 2 back to 1, not to empty.

In the system: In a plain Bloom filter, you can't delete: clearing an item's bits might clear bits that other items also need, creating false negatives. A counting Bloom filter replaces each bit with a small counter:

• Add: increment the k counters.
• Remove: decrement the k counters.
• Check: all k counters greater than 0 → probably present.

Figure: counters let you remove an item without breaking others that share its slots.

In the chapter's code, "asha" and "ravi" are added, "asha" is removed, and "ravi" is still found.

Costs and cautions:

• Memory: each slot is a counter, often 4 bits, so roughly 4× a plain Bloom filter.
• Only remove what you added, or counters go wrong and can create false negatives.
• Counters can overflow if many items share a slot; 4 bits is usually enough when the filter is sized properly.

Alternatives with deletes and less memory exist, such as cuckoo filters. Know the name; the idea is the same trade.

Memory code: "Tallies, not ticks, so you can rub one out."

---