Non-empty bins with simple tabulation hashing

DOI10.1137/1.9781611975482.153MaRDI QIDQ5236342zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

Recommendations

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

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)