(algorithm)
Definition: A probabilistic algorithm to quickly test membership in a large set using multiple hash functions into a single array of bits.
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
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 Wed Nov 23 11:50:35 2005.
HTML page formatted Wed Nov 23 11:56:52 2005.
Cite this as:
Paul E. Black, "Bloom filter", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/bloomFilter.html
