Bloom Filter

A 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 positive retrieval results are possible, but false negatives are not; i.e. a query returns either "inside set (may be wrong)" or "definitely not in set". 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.

Read more about Bloom Filter:  Algorithm Description, Space and Time Advantages, Probability of False Positives, Interesting Properties, Examples, Alternatives

Other articles related to "bloom filter, bloom filters":

Extensions and Applications - Attenuated Bloom Filters
... An attenuated bloom filter of depth D can be viewed as an array of D normal bloom filters ... the context of service discovery in a network, each node stores regular and attenuated bloom filters locally ... The regular or local bloom filter indicates which services are offered by the node itself ...

Famous quotes containing the word bloom:

    Martha: “What is Autumn?” Jan: “A second spring, where the leaves imitate the flowers. Maybe it would be so too with human beings that you would see bloom if only you helped them with your patience.”
    Albert Camus (1913–1960)