Building a Better Bloom Filter

DSpace/Manakin Repository

Building a Better Bloom Filter

Citable link to this page


Title: Building a Better Bloom Filter
Author: Kirsch, Adam; Mitzenmacher, Michael D.

Note: Order does not necessarily reflect citation order of authors.

Citation: Kirsch, Adam and Michael Mitzenmacher. Building a Better Bloom Filter. Harvard Computer Science Group Technical Report TR-02-05.
Full Text & Related Files:
Abstract: A 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.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search