Less Hashing, Same Performance: Building a Better Bloom Filter
Lists
Only you see this
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) + ih 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.
BibTeX
@inproceedings{kirsch2006less,
author = {Adam Kirsch and Michael Mitzenmacher},
title = {{Less Hashing, Same Performance: Building a Better Bloom Filter}},
booktitle = {ESA},
year = {2006},
doi = {10.1007/11841036\_42},
}Loading related content...