Load Thresholds for Cuckoo Hashing with Overlapping Blocks

Author Stefan Walzer



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.102.pdf
  • Filesize: 483 kB
  • 10 pages

Document Identifiers

Author Details

Stefan Walzer
  • Technische Universität Ilmenau, Germany

Cite AsGet BibTex

Stefan Walzer. Load Thresholds for Cuckoo Hashing with Overlapping Blocks. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 102:1-102:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.102

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Mathematics of computing → Probabilistic algorithms
  • Theory of computation → Bloom filters and hashing
Keywords
  • Cuckoo Hashing
  • Unaligned Blocks
  • Hypergraph Orientability
  • Load Thresholds
  • Randomised Algorithms

Metrics

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

References

  1. David Aldous and J. Michael Steele. The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence, pages 1-72. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. URL: http://dx.doi.org/10.1007/978-3-662-09444-0_1.
  2. Stephan Beyer. Analysis of the Linear Probing Variant of Cuckoo Hashing. Master’s thesis, Technische Universität Ilmenau, 2012. URL: http://gso.gbv.de/DB=2.1/PPNSET?PPN=685166759.
  3. 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.
  4. 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: http://dx.doi.org/10.1007/978-3-642-14165-2_19.
  5. Martin Dietzfelbinger and Christoph Weidling. Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. In Proc. 32nd ICALP, pages 166-178, 2005. URL: http://dx.doi.org/10.1007/11523468_14.
  6. 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: http://dx.doi.org/10.1016/j.tcs.2007.02.054.
  7. 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.
  8. 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: http://dx.doi.org/10.1007/s00224-004-1195-x.
  9. Nikolaos Fountoulakis, Megha Khosla, and Konstantinos Panagiotou. The Multiple-Orientability Thresholds for Random Hypergraphs. In Proc. 22nd SODA, pages 1222-1236, 2011. URL: http://www.siam.org/proceedings/soda/2011/SODA11_092_fountoulakisn.pdf.
  10. Nikolaos Fountoulakis and Konstantinos Panagiotou. Orientability of Random Hypergraphs and the Power of Multiple Choices. In Proc. 37th ICALP (1), pages 348-359, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_30.
  11. Nikolaos Fountoulakis and Konstantinos Panagiotou. Sharp Load Thresholds for Cuckoo Hashing. Random Struct. Algorithms, 41(3):306-333, 2012. URL: http://dx.doi.org/10.1002/rsa.20426.
  12. Alan M. Frieze and Páll Melsted. Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hash Tables. Random Struct. Algorithms, 41(3):334-364, 2012. URL: http://dx.doi.org/10.1002/rsa.20427.
  13. Pu Gao and Nicholas C. Wormald. Load Balancing and Orientability Thresholds for Random Hypergraphs. In Proc. 42nd STOC, pages 97-104, 2010. URL: http://dx.doi.org/10.1145/1806689.1806705.
  14. Svante Janson and Malwina J. Luczak. A simple solution to the k-core problem. Random Struct. Algorithms, 30(1-2):50-62, 2007. URL: http://dx.doi.org/10.1002/rsa.20147.
  15. M. Leconte, M. Lelarge, and L. Massoulié. Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing. In Proc. 24th SODA, pages 35-46, 2013. URL: http://dl.acm.org/citation.cfm?id=2627817.2627820.
  16. Mathieu Leconte. Double hashing thresholds via local weak convergence. In 51st Annual Allerton Conference on Communication, Control, and Computing, pages 131-137, 2013. URL: http://dx.doi.org/10.1109/Allerton.2013.6736515.
  17. 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: http://dx.doi.org/10.1007/978-3-642-04128-0_60.
  18. Marc Lelarge. A New Approach to the Orientation of Random Hypergraphs. In Proc. 23rd SODA, pages 251-264, 2012. URL: http://dl.acm.org/citation.cfm?id=2095139.
  19. Michael Molloy. Cores in random hypergraphs and boolean formulas. Random Struct. Algorithms, 27(1):124-135, 2005. URL: http://dx.doi.org/10.1002/rsa.20061.
  20. 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.
  21. Ely Porat and Bar Shalem. A Cuckoo Hashing Variant with Improved Memory Utilization and Insertion Time. In Proc. 22nd DCC, 2012. URL: http://dx.doi.org/10.1109/DCC.2012.41.
  22. Stefan Walzer. Load thresholds for cuckoo hashing with overlapping blocks. CoRR, abs/1707.06855, 2017. URL: http://arxiv.org/abs/1707.06855.
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