The power of two choices with simple tabulation

DOI10.1137/1.9781611974331.CH111MaRDI QIDQ4575695zbMATH OpenOpenAlexFDO

Authors Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Data structures (68P05) Randomized algorithms (68W20)

Abstract: The power of two choices is a classic paradigm for load balancing when assigning $m$ balls to $n$ bins. When placing a ball, we pick two bins according to two hash functions $h_0$ and $h_1$, and place the ball in the least loaded bin. Assuming fully random hash functions, when $m=O(n)$, Azar et al.~[STOC'94] proved that the maximum load is $lglgn+O(1)$ with high probability. In this paper, we investigate the power of two choices when the hash functions $h_0$ and $h_1$ are implemented with simple tabulation, which is a very efficient hash function evaluated in constant time. Following their analysis of Cuckoo hashing [J.ACM'12], Pv{a}trac{s}cu and Thorup claimed that the expected maximum load with simple tabulation is $O(lglgn)$. This did not include any high probability guarantee, so the load balancing was not yet to be trusted. Here, we show that with simple tabulation, the maximum load is $O(lglgn)$ with high probability, giving the first constant time hash function with this guarantee. We also give a concrete example where, unlike with fully random hashing, the maximum load is not bounded by $lglgn+O(1)$, or even $(1+o(1))lglgn$ with high probability. Finally, we show that the expected maximum load is $lglgn+O(1)$, just like with fully random hashing.

Recommendations

• Power of \(d\) choices with simple tabulation
• Perfectly balanced allocation
• Balanced allocations (extended abstract)
• Derandomized Balanced Allocation
• Balanced Allocations

Cited in

(7)

• Efficient hashing with lookups in two memory accesses
• Power of \(d\) choices with simple tabulation
• Non-empty bins with simple tabulation hashing
• Hashing, load balancing and multiple choice
• Balanced allocation on dynamic hypergraphs
• Balanced allocation on hypergraphs
• What if we tried less power? Lessons from studying the power of choices in hashing-based data structures

This page was built for publication: The power of two choices with simple tabulation

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