Title: Balls and Bins: Smaller Hash Families and Faster Evaluation.
Abstract: A fundamental fact in the analysis of randomized algorithms is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n/\log\log n)$ balls. In various applications, however, the assumption that a truly random hash function is available is not always valid, and explicit functions are required. In this paper we study the size of families (or, equivalently, the description length of their functions) that guarantee a maximal load of $O(\log n/\log\log n)$ with high probability, as well as the evaluation time of their functions. Whereas such functions must be described using $\Omega(\log n)$ bits, the best upper bound was formerly $O(\log^{2}n/\log\log n)$ bits, which is attained by $O(\log n/\log\log n)$-wise independent functions. Traditional constructions of $O(\log n/\log\log n)$-wise independent functions offer an evaluation time of $O(\log n/\log\log n)$, which according to Siegel's lower bound [A. Siegel, Proceedings of...
Publication Year: 2011
Publication Date: 2011-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot