Less hashing, same performance: Building a better Bloom filter

By Adam Kirsch, Michael M. Mitzenmacher. Random Struct. Algorithms, 2006

438 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Theory and Practice of Bloom Filters for Distributed Systems (2012, background): “Kirsch and Mitzenmacher have shown [16] that it requires only two independent hash functions,h1(x) and h2(x), to generate additional “pseudo” hashes defined as:”
bLSM: a general purpose log structured merge tree (2012, methodology): “Our Bloom filter is based upon double hashing [17].”
Cuckoo Filter: Practically Better Than Bloom (2014, methodology): “In addition, a performance optimization is applied to speed up lookups and inserts by doing less hashing [16].”
Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage (2014, methodology): “In [19] the hash values for k hash functions Hj were derived as proposed in [8] from a linear combination of the hash values of two hash functions g and h by the double hashing scheme Hj(b) := g(b) + j · h(b), j ∈ {0, . . . , k − 1}.”
A Novel Error-Tolerant Anonymous Linking Code (2011, methodology): “They show that only two independent hash functions are necessary to implement a Bloom filter with k hash functions without any increase in the asymptotic false positive probability [41].”
Practical Multi-party Private Set Intersection from Symmetric-Key Techniques (2017, background): “hashing[21], each insert only requires two hash functions h1(x) and h2(x).”