Less Hashing Same Performance Building a Better Bloom Filter 2008 (10.1.1.15

Less Hashing, Same Performance: Building a Better Bloom FilterAdam Kirsch,* Michael Mitzenmacher† Harvard School of Engineering and Applied Sciences, Cambridge, Massachusetts02138; e-mails: {kirsch, michaelm}@eecs.harvard.eduReceived 7 July 2006; accepted 11 July 2007 Published online 15 May 2008 in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/rsa.20208ABSTRACT: A standard technique from the hashing literature is to use two hash functions h1(x) and h2(x) to simulate additional ha