Cuckoo filter: simplification and analysis

DOI10.4230/LIPICS.SWAT.2016.8MaRDI QIDQ5369510zbMATH OpenOpenAlexFDO

Authors David Eppstein

Publication date 17 October 2017

Full work available at URL https://arxiv.org/abs/1604.06067

zbMATH Keywords

approximate setBloom filtercuckoo filtercuckoo hashing

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: The cuckoo filter data structure of Fan, Andersen, Kaminsky, and Mitzenmacher (CoNEXT 2014) performs the same approximate set operations as a Bloom filter in less memory, with better locality of reference, and adds the ability to delete elements as well as to insert them. However, until now it has lacked theoretical guarantees on its performance. We describe a simplified version of the cuckoo filter using fewer hash function calls per query. With this simplification, we provide the first theoretical performance guarantees on cuckoo filters, showing that they succeed with high probability whenever their fingerprint length is large enough.

Recommendations

• Adaptive Cuckoo Filters
• Adaptive cuckoo filters
• Xor Filters
• An optimal bloom filter replacement
• Cache-, hash-, and space-efficient bloom filters

Cited in

(8)

• CuCoTrack: cuckoo filter based connection tracking
• Binary fuse filters: fast and smaller than xor filters
• Adaptive cuckoo filters
• Xor Filters
• Adaptive Cuckoo Filters
• Stable Synchronous Propagation of Signals by Feedforward Networks
• Insertion time of random walk cuckoo hashing below the peeling threshold
• Support optimality and adaptive cuckoo filters

This page was built for publication: Cuckoo filter: simplification and analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369510)