1. 16

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.

  1. 6

    The central idea in this paper has become a standard trick used in many implementations, and should be known by any bloom filter implementer. Mitzenmacher’s papers are a wonderful combination of theory and practice. (His other famous bloom filter trick is “compressed bloom filters”, which is useful whenever a bloom filter must be sent over a bandwidth-limited medium.)