counting Bloom filter
A Bloom filter variant that keeps a small counter instead of a single bit in each position, so items can be removed.
In more detail
Adding increments k counters and removing decrements them; a query checks that all k counters are above zero. The price is several times more memory than a plain bit array. Removing an item that was never added corrupts the counts, so deletions must be trusted.
Related terms
- Bloom filter — A compact, probabilistic set that can say "definitely not present" or "probably present", using a bit array and several hash functions.
Taught in
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers