Carleton University
Technical Report TR-07-07
March 1, 2007
On the False-Positive Rate of Bloom Filters
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, Yihui Tang
Abstract
Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed the probability of such erroneous answers, called the false-positive rate, and Blooms analysis has appeared in many publications throughout the years. We show that Blooms analysis is incorrect and give a correct analysis.