A New Analysis of the False-Positive Rate of a Bloom Filter

Published

October 15, 2010

Author(s)

Ken Christensen, Allen L. Roginsky, Miguel Jimeno

Abstract

A Bloom filter is a space-efficient data structure used for probabilistic set membership testing. When testing an object for set membership, a Bloom filter may give a false positive. The analysis of the false positive rate is key to understanding the Bloom filter and applications that use it. We show experimentally that the classic analysis for false positive rate is wrong. We formally derive a correct formula using a balls-and-bins model and show how to numerically compute the new, correct formula in a stable manner. We also prove that the new formula always results in a predicted greater false positive rate than the classic formula. This correct formula is numerically compared to the classic formula for relative error for a small Bloom filter the relative error is shown to be significant.

Citation

Information Processing Letters

Volume

110

Issue

21

Pub Type

Journals

Download Paper

https://doi.org/10.1016/j.ipl.2010.07.024

Local Download

Keywords

data structures, analysis of algorithms, Bloom filters

Citation

Christensen, K. , Roginsky, A. and Jimeno, M. (2010), A New Analysis of the False-Positive Rate of a Bloom Filter, Information Processing Letters, [online], https://doi.org/10.1016/j.ipl.2010.07.024, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=903775 (Accessed April 20, 2024)