Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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

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 June 17, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created October 14, 2010, Updated October 12, 2021