Document Open Access Logo

Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold

Author Stefan Walzer

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.87.pdf
  • Filesize: 0.71 MB
  • 11 pages

Document Identifiers

Author Details

Stefan Walzer
  • Universität zu Köln, Germany

Funding

  • Walzer, Stefan: DFG grant WA 5025/1-1.

Acknowledgements

I would like to thank Martin Dietzfelbinger for providing several useful comments that helped with improving the presentation of this paper as well as an anonymous reviewer who gave useful feedback regarding the technical argument.

Cite AsGet BibTex

Stefan Walzer. Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 87:1-87:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.87

Abstract

Most hash tables have an insertion time of 𝒪(1), often qualified as "expected" and/or "amortised". While insertions into cuckoo hash tables indeed seem to take 𝒪(1) expected time in practice, only polylogarithmic guarantees are proven in all but the simplest of practically relevant cases. Given the widespread use of cuckoo hashing to implement compact dictionaries and Bloom filter alternatives, closing this gap is an important open problem for theoreticians. In this paper, we show that random walk insertions into cuckoo hash tables take 𝒪(1) expected amortised time when any number k ≥ 3 of hash functions is used and the load factor is below the corresponding peeling threshold (e.g. ≈0.81 for k = 3). To our knowledge, this is the first meaningful guarantee for constant time insertion for cuckoo hashing that works for k ∈ {3,…,9}. In addition to being useful in its own right, we hope that our key-centred analysis method can be a stepping stone on the path to the true end goal: 𝒪(1) time insertions for all load factors below the load threshold (e.g. ≈0.91 for k = 3).

Subject Classification

ACM Subject Classification
  • Theory of computation → Bloom filters and hashing
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Random graphs
Keywords
  • Cuckoo Hashing
  • Random Walk
  • Random Hypergraph
  • Peeling
  • Cores

Metrics

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

Related Versions

References

  1. Anders Aamand, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. Power of d choices with simple tabulation. In 45th ICALP, volume 107 of LIPIcs, pages 5:1-5:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.5.
  2. 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: https://doi.org/10.1007/s00453-013-9840-x.
  3. Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat, and Clifford Stein. Incremental edge orientation in forests. In 29th ESA, volume 204 of LIPIcs, pages 12:1-12:18, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.12.
  4. Julie Anne Cain, Peter Sanders, and Nicholas C. Wormald. The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In Proc. 18th SODA, pages 469-476, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283433.
  5. Colin Cooper. The cores of random hypergraphs with a given degree sequence. Random Struct. Algorithms, 25(4):353-375, 2004. URL: https://doi.org/10.1002/rsa.20040.
  6. Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink. Tight thresholds for cuckoo hashing via XORSAT. In Proc. 37th ICALP (1), pages 213-225, 2010. URL: https://doi.org/10.1007/978-3-642-14165-2_19.
  7. Martin Dietzfelbinger and Christoph Weidling. Balanced allocation and dictionaries with tightly packed constant size bins. Theor. Comput. Sci., 380(1-2):47-68, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.054.
  8. David Eppstein. Cuckoo filter: Simplification and analysis. In Proc. 15th SWAT, pages 8:1-8:12, 2016. URL: https://doi.org/10.4230/LIPIcs.SWAT.2016.8.
  9. Bin Fan, David G. Andersen, and Michael Kaminsky. Cuckoo filter: Better than Bloom. ;login:, 38(4), 2013. URL: https://www.usenix.org/publications/login/august-2013-volume-38-number-4/cuckoo-filter-better-bloom.
  10. Bin Fan, David G. Andersen, Michael Kaminsky, and Michael Mitzenmacher. Cuckoo filter: Practically better than bloom. In Proc. 10th CoNEXT, pages 75-88, 2014. URL: https://doi.org/10.1145/2674005.2674994.
  11. Daniel Fernholz and Vijaya Ramachandran. The k-orientability thresholds for g_n,p. In Proc. 18th SODA, pages 459-468, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283432.
  12. Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul G. Spirakis. Space efficient hash tables with worst case constant access time. Theory Comput. Syst., 38(2):229-248, 2005. URL: https://doi.org/10.1007/s00224-004-1195-x.
  13. Nikolaos Fountoulakis, Megha Khosla, and Konstantinos Panagiotou. The multiple-orientability thresholds for random hypergraphs. Combinatorics, Probability & Computing, 25(6):870-908, 2016. URL: https://doi.org/10.1017/S0963548315000334.
  14. Nikolaos Fountoulakis and Konstantinos Panagiotou. Sharp load thresholds for cuckoo hashing. Random Struct. Algorithms, 41(3):306-333, 2012. URL: https://doi.org/10.1002/rsa.20426.
  15. Nikolaos Fountoulakis, Konstantinos Panagiotou, and Angelika Steger. On the insertion time of cuckoo hashing. SIAM J. Comput., 42(6):2156-2181, 2013. URL: https://doi.org/10.1137/100797503.
  16. Alan M. Frieze and Tony Johansson. On the insertion time of random walk cuckoo hashing. Random Struct. Algorithms, 54(4):721-729, 2019. URL: https://doi.org/10.1002/rsa.20808.
  17. Alan M. Frieze, Páll Melsted, and Michael Mitzenmacher. An analysis of random-walk cuckoo hashing. SIAM J. Comput., 40(2):291-308, 2011. URL: https://doi.org/10.1137/090770928.
  18. Alan M. Frieze and Samantha Petti. Balanced allocation through random walk. Inf. Process. Lett., 131:39-43, 2018. URL: https://doi.org/10.1016/j.ipl.2017.11.010.
  19. Svante Janson and Malwina J. Luczak. A simple solution to the k-core problem. Random Struct. Algorithms, 30(1-2):50-62, 2007. URL: https://doi.org/10.1002/rsa.20147.
  20. Megha Khosla. Balls into bins made faster. In Proc. 21st ESA, pages 601-612, 2013. URL: https://doi.org/10.1007/978-3-642-40450-4_51.
  21. Adam Kirsch, Michael Mitzenmacher, and Udi Wieder. More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput., 39(4):1543-1561, 2009. URL: https://doi.org/10.1137/080728743.
  22. Mathieu Leconte. Double hashing thresholds via local weak convergence. In Proc. 51st Allerton, pages 131-137, 2013. URL: https://doi.org/10.1109/Allerton.2013.6736515.
  23. Eric Lehman and Rina Panigrahy. 3.5-way cuckoo hashing for the price of 2-and-a-bit. In Proc. 17th ESA, pages 671-681, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_60.
  24. Marc Lelarge. A new approach to the orientation of random hypergraphs. In Proc. 23rd SODA, pages 251-264. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.23.
  25. Michael Mitzenmacher and Justin Thaler. Peeling arguments and double hashing. In Proc. 50th Allerton, pages 1118-1125, 2012. URL: https://doi.org/10.1109/Allerton.2012.6483344.
  26. Michael Molloy. Cores in random hypergraphs and Boolean formulas. Random Struct. Algorithms, 27(1):124-135, 2005. URL: https://doi.org/10.1002/rsa.20061.
  27. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122-144, 2004. URL: https://doi.org/10.1016/j.jalgor.2003.12.002.
  28. Boris Pittel, Joel Spencer, and Nicholas C. Wormald. Sudden emergence of a giant k-core in a random graph. J. Comb. Theory, Ser. B, 67(1):111-151, 1996. URL: https://doi.org/10.1006/jctb.1996.0036.
  29. Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-25209-0.
  30. Stefan Walzer. Load thresholds for cuckoo hashing with overlapping blocks. In Proc. 45th ICALP, pages 102:1-102:10, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.102.
  31. Stefan Walzer. Peeling close to the orientability threshold: Spatial coupling in hashing-based data structures. In Proc. 32nd SODA, pages 2194-2211. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.131.
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 Imprint Privacy Contact