Building a Better Bloom Filter
MetadataShow full item record
CitationKirsch, Adam and Michael Mitzenmacher. Building a Better Bloom Filter. Harvard Computer Science Group Technical Report TR-02-05.
AbstractA technique from the hashing literature is to use two hash functions h1(x) and h2(x) to simulate additional hash functions of the form gi(x) = h1(x) + ih2(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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:23017278
- FAS Scholarly Articles