Non-empty Bins with Simple Tabulation Hashing

Anders Aamand; Mikkel Thorup

doi:10.1137/1.9781611975482.153

Non-empty Bins with Simple Tabulation Hashing

Datalogisk Institut

Abstract

We consider the hashing of a set X ⊆ U with |X| = m using a simple tabulation hash function h : U → [n] = {0,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. Our results imply that if we implement the hashing with simple tabulation, we obtain the same low false-positive probability for any possible input.

Originalsprog	Engelsk
Titel	Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
Redaktører	Timothy M. Chan
Forlag	Society for Industrial and Applied Mathematics
Publikationsdato	2 jan. 2019
Sider	2498-2512
ISBN (Elektronisk)	978-1-61197-548-2
DOI	https://doi.org/10.1137/1.9781611975482.153
Status	Udgivet - 2 jan. 2019
Begivenhed	30th Annual ACM-SIAM Symposium on Discrete Algorithms : SODA19 - San Diego, USA Varighed: 6 jan. 2019 → 9 jan. 2019

Konference

Konference	30th Annual ACM-SIAM Symposium on Discrete Algorithms
Land/Område	USA
By	San Diego
Periode	06/01/2019 → 09/01/2019

Adgang til dokumentet

10.1137/1.9781611975482.153

1.9781611975482.153Forlagets udgivne version, 657 KB

https://epubs.siam.org/doi/10.1137/1.9781611975482.153

Citationsformater

@inproceedings{ad5e74abfdb841f6ac9e72f20eaf6bca,

title = "Non-empty Bins with Simple Tabulation Hashing",

abstract = "We consider the hashing of a set X ⊆ U with |X| = m using a simple tabulation hash function h : U → [n] = {0,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. Our results imply that if we implement the hashing with simple tabulation, we obtain the same low false-positive probability for any possible input.",

author = "Anders Aamand and Mikkel Thorup",

year = "2019",

month = jan,

day = "2",

doi = "10.1137/1.9781611975482.153",

language = "English",

pages = "2498--2512",

editor = "Chan, {Timothy M.}",

booktitle = "Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "30th Annual ACM-SIAM Symposium on Discrete Algorithms<br/> : SODA19 ; Conference date: 06-01-2019 Through 09-01-2019",

}

TY - GEN

T1 - Non-empty Bins with Simple Tabulation Hashing

AU - Aamand, Anders

AU - Thorup, Mikkel

PY - 2019/1/2

Y1 - 2019/1/2

N2 - We consider the hashing of a set X ⊆ U with |X| = m using a simple tabulation hash function h : U → [n] = {0,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. Our results imply that if we implement the hashing with simple tabulation, we obtain the same low false-positive probability for any possible input.

AB - We consider the hashing of a set X ⊆ U with |X| = m using a simple tabulation hash function h : U → [n] = {0,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. Our results imply that if we implement the hashing with simple tabulation, we obtain the same low false-positive probability for any possible input.

U2 - 10.1137/1.9781611975482.153

DO - 10.1137/1.9781611975482.153

M3 - Article in proceedings

SP - 2498

EP - 2512

BT - Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Chan, Timothy M.

PB - Society for Industrial and Applied Mathematics

T2 - 30th Annual ACM-SIAM Symposium on Discrete Algorithms<br/>

Y2 - 6 January 2019 through 9 January 2019

ER -

Non-empty Bins with Simple Tabulation Hashing

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater