Bloom Filters -- A Tutorial, Analysis, and Survey


James Blustein
Amal El-Maazawi

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2


Bloom filters use superimposed hash transforms to provide a probabilistic membership test. The only types of errors are false positives (non-members being reported as members). Non-members are typically detected quickly (requiring only two probes in the optimal case).

This article surveys modern applications of this technique (e.g., in spell checking and Web caching software) and provides a detailed analysis of their performance, in theory and practice. The article concludes with practical advice about implementing this useful and intriguing technique.

Tech Report Number: 
Report Date: 
December 10, 2002
CS-2002-10.pdf222.55 KB