2008-10-31
On the false-positive rate of Bloom filters
Publication
Publication
Information Processing Letters
,
Volume 108
-
Issue 4
p. 210-
213
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 Bloom's analysis has appeared in many publications throughout the years. We show that Bloom's analysis is incorrect and give a correct analysis.
| Additional Metadata | |
|---|---|
| Keywords | Analysis of algorithms, Data structures |
| Persistent URL | dx.doi.org/10.1016/j.ipl.2008.05.018 |
| Journal | Information Processing Letters |
| Citation |
Bose, P, Guo, H. (Hua), Kranakis, E, Maheshwari, A, Morin, P, Morrison, J. (Jason), … Tang, Y. (Yihui). (2008). On the false-positive rate of Bloom filters. Information Processing Letters, 108(4), 210–213. doi:10.1016/j.ipl.2008.05.018
|