Cuckoo Filters


Cuckoo Filters are probabilistic data structures similar to Bloom Filters that provides support for removing elements without significantly degrading space and performance.

Instead of storing the elements themselves, it stores a fingerprint obtained by using a checksum. This allows for item removal without false negatives (assuming you do not try and remove an item not contained in the filter.

For applications that store many items and target low false-positive rates, Cuckoo Filters can have a lower space overhead than Bloom Filters.

More information is available in the paper by Andersen, Kaminsky, and Mitzenmacher titled "Cuckoo Filter: Practically Better Than Bloom":

http://www.pdl.cmu.edu/PDL-FTP/FS/cuckoo-conext2014.pdf