NIST

Bloom filter

(data structure)

Definition: A data structure with a probabilistic algorithm to quickly test membership in a large set using multiple hash functions into a single array of bits.

Aggregate parent (I am a part of or used in ...)
hsadelta.

Aggregate child (... is a part of or used in me.)
array of bits, hash function.

See also invertible Bloom lookup table, locality-sensitive hashing.

Note: A Bloom filter is good for secret sharing: giving a Bloom filter lets someone see if you have an item (it is found in the Bloom filter), but it is impractical to recreate the whole collection.

Author: PEB

Implementation

Arash Partow's implementations (C++, Object Pascal) (go to Download, at the bottom).

More information

The Bose, Guo, Kranakis, et. al. paper below shows that "The actual false-positive rate is strictly larger than" Bloom's formula.
Bloom_filter [Wikipedia] gives many variants and extensions. Trade-offs and engineering techniques with links to sites with recent papers, hash functions, etc. Another explanation typo: probability of false positive is missing a minus sign; exponent should be ... e-kn/m. Using Bloom filters. Language is Perl. Jason Davies' interactive animation helps people understand how a Bloom filter works.

Burton Bloom, Space/time trade-offs in hash coding with allowable errors, CACM, 13(7):422-426, July 1970.
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, and Yihui Tang, On the False-Positive Rate of Bloom Filters, Technical Report TR-07-07, Carleton University - School of Computer Science, 1 March 2007. Available at http://www.scs.carleton.ca/research/tech_reports/index.php?Abstract=tr-07-07_0007
They also conclude that "Our upper-bounds show that, for large enough values of m with small values of k, the difference between pk and the actual false-positive rate is negligible."


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 9 November 2020.
HTML page formatted Mon Nov 9 16:41:25 2020.

Cite this as:
Paul E. Black, "Bloom filter", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 9 November 2020. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bloomFilter.html