Load Thresholds for Cuckoo Hashing with Overlapping Blocks

DOI10.4230/LIPIcs.ICALP.2018.102zbMath1499.68082arXiv1707.06855OpenAlexW2963131345MaRDI QIDQ5002785

Stefan Walzer

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1707.06855

zbMATH Keywords

cuckoo hashingrandomised algorithmshypergraph orientabilityload thresholdsunaligned blocks

Mathematics Subject Classification ID

Data structures (68P05) Randomized algorithms (68W20)

Related Items (2)

Dynamic space efficient hashing ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Space efficient hash tables with worst case constant access time
• Balanced allocation and dictionaries with tightly packed constant size bins
• Load balancing and orientability thresholds for random hypergraphs
• Sharp load thresholds for cuckoo hashing
• Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables
• A simple solution to the k‐core problem
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Orientability of Random Hypergraphs and the Power of Multiple Choices
• 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit
• Cuckoo hashing
• Cores in random hypergraphs and Boolean formulas
• The Multiple-orientability Thresholds for Random Hypergraphs
• Automata, Languages and Programming
• Convergence of Multivariate Belief Propagation, with Applications to Cuckoo Hashing and Load Balancing
• A new approach to the orientation of random hypergraphs

This page was built for publication: Load Thresholds for Cuckoo Hashing with Overlapping Blocks