Some systems need fast "have we seen this?" checks, but they also need to remove items later.

A standard Bloom filter is great for fast membership checks, but it cannot safely delete individual items. Once several items share the same bits, clearing those bits may break other items.

A Cuckoo Filter solves that problem in a different way. Like a Bloom filter, it answers one question:

Is this item probably present, or definitely absent?

Instead of setting shared bits, it stores small fingerprints of items inside buckets. Because it stores something removable, deletion is much easier.

It can still return false positives. But if it is maintained correctly, it should not return false negatives for items that were added and not deleted.

This chapter explains how Cuckoo Filters store items, how insertion and deletion work, where they fit, and how they compare to Bloom Filters.

Standard Bloom Filters cannot safely delete individual items.

When an item is added to a Bloom filter, it sets several bits to 1. Other items may use some of the same bits. If you clear those bits during deletion, you may accidentally make another item look absent.

Counting Bloom Filters work around this by using counters instead of bits. To delete an item, they decrement the counters. That works, but it uses more memory and can run into counter overflow or incorrect deletion problems.

Cuckoo Filters take another approach. They store a short fingerprint in one of two possible buckets. To delete an item, the filter removes the matching fingerprint from one of those buckets.