The Power of Two Choices with Simple Tabulation
| Autor: | Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. |
| DOI: | 10.1137/1.9781611974331.ch111 |
| Popis: | 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 $\lg \lg n + 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], P\v{a}tra\c{s}cu and Thorup claimed that the expected maximum load with simple tabulation is $O(\lg\lg n)$. 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(\lg\lg n)$ 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 $\lg \lg n + O(1)$, or even $(1+o(1))\lg \lg n$ with high probability. Finally, we show that the expected maximum load is $\lg \lg n + O(1)$, just like with fully random hashing. Comment: SODA'16 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|