Load Thresholds for Cuckoo Hashing with Overlapping Blocks

DOI10.4230/LIPICS.ICALP.2018.102MaRDI QIDQ5002785zbMATH OpenOpenAlexFDO

Authors Stefan Walzer

Publication date 28 July 2021

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

zbMATH Keywords

cuckoo hashinghypergraph orientabilityload thresholdsrandomised algorithmsunaligned blocks

Mathematics Subject Classification ID

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

Abstract: Dietzfelbinger and Weidling [DW07] proposed a natural variation of cuckoo hashing where each of $cn$ objects is assigned $k=2$ intervals of size $ell$ in a linear (or cyclic) hash table of size $n$ and both start points are chosen independently and uniformly at random. Each object must be placed into a table cell within its intervals, but each cell can only hold one object. Experiments suggested that this scheme outperforms the variant with blocks in which intervals are aligned at multiples of $ell$. In particular, the load threshold is higher, i.e. the load $c$ that can be achieved with high probability. For instance, Lehman and Panigrahy [LP09] empirically observed the threshold for $ell=2$ to be around $96.5\mathrm{\%}$ as compared to roughly $89.7\mathrm{\%}$ using blocks. They managed to pin down the asymptotics of the thresholds for large $ell$, but the precise values resisted rigorous analysis. We establish a method to determine these load thresholds for all $ellgeq2$, and, in fact, for general $kgeq2$. For instance, for $k=ell=2$ we get $approx96.4995\mathrm{\%}$. The key tool we employ is an insightful and general theorem due to Leconte, Lelarge, and Massouli'e [LLM13], which adapts methods from statistical physics to the world of hypergraph orientability. In effect, the orientability thresholds for our graph families are determined by belief propagation equations for certain graph limits. As a side note we provide experimental evidence suggesting that placements can be constructed in linear time with loads close to the threshold using an adapted version of an algorithm by Khosla [Kho13].

Cites work

• 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit
• A new approach to the orientation of random hypergraphs
• A simple solution to the k‐core problem
• Automata, Languages and Programming
• Balanced allocation and dictionaries with tightly packed constant size bins
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Cores in random hypergraphs and Boolean formulas
• Cuckoo hashing
• Load balancing and orientability thresholds for random hypergraphs
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Orientability of random hypergraphs and the power of multiple choices
• Sharp load thresholds for cuckoo hashing
• Space efficient hash tables with worst case constant access time
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The multiple-orientability thresholds for random hypergraphs
• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)

Cited in

(4)

• Dynamic space efficient hashing
• Dense peelable random uniform hypergraphs
• Fast lightweight accurate xenograft sorting
• Insertion time of random walk cuckoo hashing below the peeling threshold

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002785)