#Algorithm description:
The Bloom filter, conceived by Burton Howard Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.False positivesare possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.
An empty Bloom filter is abit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of them array positions with a uniform random distribution.
#Bloom Filter's Principle:
An example of a Bloom filter, representing the set {x, y,z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m=18 and k=3.
#Bloom Filter Application
Google BigTable uses Bloom filters to reduce the disk lookups for non-existent rows or columns. Avoiding costly disk lookups considerably increases the performance of a database query operation.[2]
The Squid Web Proxy Cache uses Bloom filters for cache digests.[3]
The Venti archival storage system uses Bloom filters to detect previously-stored data.[4]
The SPIN model checker uses Bloom filters to track the reachable state space for large verification problems.[5]
The Google Chrome web browser uses Bloom filters to speed up its Safe Browsing service.[6]
Read more:http://www.answers.com/bloom%20filter