Non-empty bins with simple tabulation hashing

DOI10.1137/1.9781611975482.153zbMATH Open1432.68079arXiv1810.13187OpenAlexW2952109546MaRDI QIDQ5236342FDOQ5236342

Authors: Anders Aamand, Mikkel Thorup 

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We consider the hashing of a set $XsubseteqU$ with $|X|=m$ using a simple tabulation hash function $h:Uo[n]=0,dots,n-1$ and analyse the number of non-empty bins, that is, the size of $h(X)$. We show that the expected size of $h(X)$ matches that with fully random hashing to within low-order terms. We also provide concentration bounds. The number of non-empty bins is a fundamental measure in the balls and bins paradigm, and it is critical in applications such as Bloom filters and Filter hashing. For example, normally Bloom filters are proportioned for a desired low false-positive probability assuming fully random hashing (see url{en.wikipedia.org/wiki/Bloom_filter}). Our results imply that if we implement the hashing with simple tabulation, we obtain the same low false-positive probability for any possible input.

Full work available at URL: https://arxiv.org/abs/1810.13187

Recommendations

• scientific article; zbMATH DE number 6351507
• Twisted tabulation hashing
• The power of two choices with simple tabulation

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Data structures (68P05)

This page was built for publication: Non-empty bins with simple tabulation hashing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236342)