Skip to content

Cuckoo Filter: Practically Better than Bloom

Authors: Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher

Published: 2014 (Conference Paper)

Source: ACM International Conference on Emerging Networking Experiments and Technologies (CoNEXT)

Algorithm: Cuckoo filter

DOI: 10.1145/2674005.2674994

Summary

Introduces cuckoo filters as a deletion-friendly approximate membership structure that can beat Bloom filters at practical false-positive rates. The paper is useful because it turns cuckoo hashing into a compact fingerprint table with strong lookup and update performance.

Abstract

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.

Primary

Paper cs.cmu.edu

Standard

DOI 10.1145/2674005.2674994

Tags

  • Cuckoo filter

  • Bloom filter

  • Approximate membership

  • Probabilistic data structures

  • Hashing

  • Networking