(algorithm)
Definition: 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.
See also locality-sensitive hashing.
Note: This involves a particular data structure, the bit array, too. 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
Wikipedia entry, which 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.
Burton Bloom, Space/time trade-offs in hash coding with allowable errors, CACM, 13(7):422-426, July 1970.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 16 May 2008.
HTML page formatted Fri May 16 16:14:44 2008.
Cite this as:
Paul E. Black, "Bloom filter", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 16 May 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bloomFilter.html
