Some systems need approximate membership checks, but also need deletion.

A Cuckoo Filter is a probabilistic membership structure similar in spirit to a Bloom Filter. It answers "probably present" or "definitely absent," but stores small fingerprints in buckets instead of setting bits.

The main attraction is that Cuckoo Filters can support deletion without rebuilding the whole filter, as long as the implementation tracks fingerprints correctly.

Standard Bloom Filters cannot safely delete individual items. When an item sets several bits, those bits may also be used by other items. Clearing them can create false negatives for items that are still present.

Counting Bloom Filters solve this by replacing bits with counters, but that costs more memory and introduces counter overflow concerns.

Cuckoo Filters take a different approach. They store short fingerprints in candidate buckets. To delete an item, the filter removes the matching fingerprint from one of its possible buckets.