Document Open Access Logo

Cuckoo Filter: Simplification and Analysis

Author David Eppstein

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.8.pdf
  • Filesize: 475 kB
  • 12 pages

Document Identifiers

Author Details

David Eppstein

Cite As Get BibTex

David Eppstein. Cuckoo Filter: Simplification and Analysis. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.8

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.

Subject Classification

Keywords
  • approximate set
  • Bloom filter
  • cuckoo filter
  • cuckoo hashing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Martin Aumüller, Martin Dietzfelbinger, and Philipp Woelfel. Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica, 70(3):428-456, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9840-x.
  2. Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422-426, 1970. URL: http://dx.doi.org/10.1145/362686.362692.
  3. Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. J. Algorithms, 55(1):58-75, 2005. URL: http://dx.doi.org/10.1016/j.jalgor.2003.12.001.
  4. Martin Dietzfelbinger and Ulf Schellbach. On risks of using cuckoo hashing with simple universal hash classes. In Proc. 20th ACM-SIAM Symp. Discrete Algorithms (SODA'09), pages 795-804, 2009. Google Scholar
  5. Martin Dietzfelbinger and Christoph Weidling. Balanced allocation and dictionaries with tightly packed constant size bins. Theoret. Comput. Sci., 380(1-2):47-68, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.02.054.
  6. David Eppstein and Michael T. Goodrich. Straggler identification in round-trip data streams via Newton’s identities and invertible Bloom filters. IEEE Trans. Knowledge and Data Engineering, 23(2):297-306, 2011. http://arxiv.org/abs/0704.3313, URL: http://dx.doi.org/10.1109/TKDE.2010.132.
  7. David Eppstein, Michael T. Goodrich, Frank Uyeda, and George Varghese. What’s the difference? Efficient set reconciliation without prior context. In Proc. ACM SIGCOMM 2011, pages 218-229, 2011. URL: http://dx.doi.org/10.1145/2018436.2018462.
  8. Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo filter: Practically better than Bloom. In Proc. 10th ACM Int. Conf. Emerging Networking Experiments and Technologies (CoNEXT'14), pages 75-88, 2014. URL: http://dx.doi.org/10.1145/2674005.2674994.
  9. Li Fan, Pei Cao, Jussara Almeida, and Andrei Broder. Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Trans. Networking, 8(3):281-293, 2000. URL: http://dx.doi.org/10.1109/90.851975.
  10. M. Grissa, A.A. Yavuz, and B. Hamdaoui. Cuckoo filter-based location-privacy preservation in database-driven cognitive radio networks. In Proc. World Symp. Computer Networks and Information Security (WSCNIS 2015), pages 1-7. IEEE, 2015. URL: http://dx.doi.org/10.1109/WSCNIS.2015.7368280.
  11. Vikas Gupta and Frank Breitinger. How cuckoo filter can improve existing approximate matching techniques. In Joshua I. James and Frank Breitinger, editors, Proc. 7th Int. Conf. Digital Forensics and Cyber Crime (ICDF2C 2015), volume 157 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pages 39-52. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-25512-5_4.
  12. Adam Kirsch, Michael D. Mitzenmacher, and Udi Wieder. More robust hashing: cuckoo hashing with a stash. SIAM J. Comput., 39(4):1543-1561, 2010. URL: http://dx.doi.org/10.1137/080728743.
  13. Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao. An optimal Bloom filter replacement. In Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 823-829. ACM, New York, 2005. Google Scholar
  14. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122-144, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2003.12.002.
  15. Mihai Pătraşcu and Mikkel Thorup. The power of simple tabulation hashing. J. ACM, 59(3):A14, 2012. URL: http://dx.doi.org/10.1145/2220357.2220361.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact