Premium
Less hashing, same performance: Building a better Bloom filter
Author(s) -
Kirsch Adam,
Mitzenmacher Michael
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20208
Subject(s) - bloom filter , hash function , randomness , computer science , filter (signal processing) , computation , algorithm , dynamic perfect hashing , theoretical computer science , hash table , universal hashing , mathematics , double hashing , statistics , programming language , computer vision
A standard technique from the hashing literature is to use two hash functions h 1 ( x ) and h 2 ( x ) to simulate additional hash functions of the form g i ( x ) = h 1 ( x ) + i h 2 ( x ). We demonstrate that this technique can be usefully applied to Bloom filters and related data structures. Specifically, only two hash functions are necessary to effectively implement a Bloom filter without any loss in the asymptotic false positive probability. This leads to less computation and potentially less need for randomness in practice. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008