The power of two choices with simple tabulation

TY - GEN

T1 - The power of two choices with simple tabulation

AU - Dahlgaard, Søren

AU - Knudsen, Mathias Bæk Tejs

AU - Rotenberg, Eva

AU - Thorup, Mikkel

N1 - Conference code: 27

PY - 2016

Y1 - 2016

N2 - 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 ho and h1, 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 + 0(1) with high probability. No such bound was known with a hash function implementable in constant time. In this paper, we investigate the power of two choices when the hash functions ho and h1 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], PǍtraş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 + 0(l), or even (1 + o(l)) lglgn with high probability. Finally, we show that the expected maximum load is lglgn + 0(1), just like with fully random hashing.

AB - 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 ho and h1, 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 + 0(1) with high probability. No such bound was known with a hash function implementable in constant time. In this paper, we investigate the power of two choices when the hash functions ho and h1 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], PǍtraş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 + 0(l), or even (1 + o(l)) lglgn with high probability. Finally, we show that the expected maximum load is lglgn + 0(1), just like with fully random hashing.

U2 - 10.1137/1.9781611974331.ch111

DO - 10.1137/1.9781611974331.ch111

M3 - Article in proceedings

SP - 1631

EP - 1642

BT - Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Krauthgamer, Robert

PB - Society for Industrial and Applied Mathematics

T2 - Annual ACM-SIAM Symposium on Discrete Algorithms 2016

Y2 - 10 January 2016 through 12 January 2016

ER -