Rumor Spreading in Random Evolving Graphs

Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Pasquale, Francesco; Silvestri, Riccardo
A standard 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.
Research areas:
Year:
2016
Type of Publication:
In Collection
Keywords:
bloom filters; double hashing; poisson convergence
JRESEARCH_BOOK_TITLE:
Random Structure and Algorithms
Pages:
456-467
ISBN:
3540388753
DOI:
10.1002/rsa
Hits: 2897

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information