Power of d Choices with Simple Tabulation

Anders Aamand, Mathias Bæk Tejs Knudsen & Mikkel Thorup
We consider the classic d-choice paradigm of Azar et al. [STOC'94] in which m balls are put into n bins sequentially as follows: For each ball we are given a choice of d bins chosen according to d hash functions and the ball is placed in the least loaded of these bins, breaking ties arbitrarily. The interest is in the number of balls in the fullest bin after all balls have been placed. In this...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.