Cuckoo filter

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

A cuckoo filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set, like a Bloom filter does. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". A cuckoo filter can also delete existing items, which is not supported by Bloom filters. In addition, for applications that store many items and target moderately low false positive rates, cuckoo filters can achieve lower space overhead than space-optimized Bloom filters.[1]

Cuckoo filters were first described in 2014.[2]

Algorithm description[edit]

A cuckoo filter uses a 4-way set-associative hash table based on cuckoo hashing to store the fingerprints of all items. Particularly, the two potential buckets in the table for a given item required by cuckoo hashing are calculated by the following two hash functions (termed as partial-key cuckoo hashing[2]):


Applying the above two hash functions to construct a cuckoo hash table enables item relocation based only on fingerprints when retrieving the original item is impossible. As a result, when inserting a new item that requires relocating an existing item , the other possible location in the table for this item kicked out from bucket is calculated by

Based on partial-key cuckoo hashing, the hash table can achieve both highly-utilization (thanks to cuckoo hashing), and compactness because only fingerprints are stored. Lookup and delete operations of a cuckoo filter are straightforward. There are a maximum of two locations to check by and . If found, the appropriate lookup or delete operation can be performed in time. More theoretical analysis of cuckoo filters can be found in the literature.[3][4]

Comparison to Bloom filters[edit]

A cuckoo filter is similar to a Bloom filter in that they both are very fast and compact, and they may both return false positives as answers to set-membership queries:

  • Space-optimal Bloom filters use bits of space per inserted key, where is the false positive rate. A cuckoo filter requires where is the hash table load factor, which can be based on the cuckoo filter's setting. Note that the information theoretical lower bound requires bits for each item.
  • On a positive lookup, a space-optimal Bloom filter requires a constant memory accesses into the bit array, whereas a cuckoo filter requires constant two lookups at most.
  • Cuckoo filters have degraded insertion speed after reaching a load threshold, when table expanding is recommended. In contrast, Bloom filters can keep inserting new items at the cost of a higher false positive rate before expansion.

Limitations[edit]

  • A cuckoo filter can only delete items that are known to be inserted before.
  • Insertion can fail and rehashing is required like other cuckoo hash tables. Note that the amortized insertion complexity is still .[5]

References[edit]

  1. ^ Michael D. Mitzenmacher. "Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters".
  2. ^ a b Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: Practically better than Bloom. Proc. 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT '14). Sydney, Australia. pp. 75–88. doi:10.1145/2674005.2674994. ISBN 9781450332798.
  3. ^ Eppstein, David (22 June 2016). Cuckoo filter: Simplification and analysis. Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs). 53. Reykjavik, Iceland. pp. 8:1–8:12. arXiv:1604.06067. doi:10.4230/LIPIcs.SWAT.2016.8.
  4. ^ Fleming, Noah. "Cuckoo Hashing and Cuckoo Filters" (PDF).
  5. ^ Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo hashing". Proc. 9th Annual European Symposium on Algorithms (ESA 2001). Lecture Notes in Computer Science. 2161. Århus, Denmark. pp. 121–133. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.

External links[edit]