Random Structures and Algorithms · 2008 · 131 citations · 12 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCryptographyData StructuresCryptographic HashingHash FunctionsHash TablesBloom FiltersHash Function DesignHash Function ImplementationHashing
Abstract 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
12
The Art of Computer Programming
G.E. Whitesides · Nuclear Science and Engineering · 1970 · 6.1K citations
Network Applications of Bloom Filters: A Survey
Andrei Broder, Michael Mitzenmacher · Internet Mathematics · 2004 · 2K citations · Full text
John Hawkes, P. Billingsley · Journal of the Royal Statistical Society Series A (General) · 1987 · 1.7K citations