Aamand, Anders ;
Bæk Tejs Knudsen, Mathias ;
Thorup, Mikkel
Power of d Choices with Simple Tabulation
Abstract
We consider the classic dchoice 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 paper we suppose that the d hash functions are simple tabulation hash functions which are easy to implement and can be evaluated in constant time. Generalising a result by Dahlgaard et al. [SODA'16] we show that for an arbitrary constant d >= 2 the expected maximum load is at most (lg lg n)/(lg d) + O(1). We further show that by using a simple tiebreaking algorithm introduced by Vöcking [J.ACM'03] the expected maximum load is reduced to (lg lg n)/(d lg phi_d) + O(1) where phi_d is the rate of growth of the dary Fibonacci numbers. Both of these expected bounds match those known from the fully random setting.
The analysis by Dahlgaard et al. relies on a proof by Patrascu and Thorup [J.ACM'11] concerning the use of simple tabulation for cuckoo hashing. We require a generalisation to d>2 hash functions, but the original proof is an 8page tour de force of adhoc arguments that do not appear to generalise. Our main technical contribution is a shorter, simpler and more accessible proof of the result by Patrascu and Thorup, where the relevant parts generalise nicely to the analysis of d choices.
BibTeX  Entry
@InProceedings{aamand_et_al:LIPIcs:2018:9009,
author = {Anders Aamand and Mathias Bæk Tejs Knudsen and Mikkel Thorup},
title = {{Power of d Choices with Simple Tabulation}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {5:15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9009},
URN = {urn:nbn:de:0030drops90096},
doi = {10.4230/LIPIcs.ICALP.2018.5},
annote = {Keywords: Hashing, Load Balancing, Balls and Bins, Simple Tabulation}
}
04.07.2018
Keywords: 

Hashing, Load Balancing, Balls and Bins, Simple Tabulation 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 