Cuckoo Filter: Practically Better Than Bloom
By Bin Fan, D. Andersen, Michael Kaminsky, Michael M. Mitzenmacher. Conference on Emerging Network Experiment and Technology, 2014
811 citations recorded by the source corpus.
In many networking systems, Bloom filters are used for high-speed set membership tests. They permit a small fraction of false positive answers with very good space efficiency. However, they do not permit deletion of items from the set, and previous attempts to extend "standard" Bloom filters to support deletion all degrade either space or performance. We propose a new data structure called the cuckoo filter that can replace Bloom filters for approximate set membership tests. Cuckoo filters support adding and removing items dynamically while achieving even higher performance than Bloom filters. For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters. Our experimental results also show that cuckoo filters outperform previous data structures that extend Bloom filters to support deletions substantially in both time and space.
Subfields: Computer Networks and Communications, Materials Chemistry
View Paper: https://www.semanticscholar.org/paper/3a2f37d3648592ffb42155c28f71894ad61937fe
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Aruna Prasad Seneviratne
- Salil S. Kanhere
- Dean M. Tullsen
- Tim Kraska
- Helge Janicke
- Nuwan Jayasena
- Rui Miao
- Sanjay Kumar Jha
Citations in the corpus
- The Case for Learned Index Structures (2017, background): “Because of their importance for database systems and many other applications, indexes have been extensively tuned over the past decades to be more memory, cache and/or CPU efficient [11, 29, 36, 59].”
- SilkRoad: Making Stateful Layer-4 Load Balancing Fast and Cheap Using Switching ASICs (2017, methodology): “Compact connection match keys by hash digests: To reduce the size of the match field of each connection entry, we store a hash digest instead of the 5-tuple as proposed in [21].”
- Horton Tables: Fast Hash Tables for In-Memory Data-Intensive Computing (2016, methodology): “To this end, this paper presents Horton tables,2 a carefully retrofitted bucketized cuckoo hash table, which trades a small amount of space for achieving positive and negative lookups that touch close to 1 bucket apiece.”
- A Survey of COVID-19 Contact Tracing Apps (2020, methodology): “The server hashes these values in a Cuckoo filter [59] before advertising these to the other users.”