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

Taught in

References