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
Famous quotes containing the word bloom:
“Half-opening her lips to the frost’s morning sigh, how strangely the rose has smiled on a swift-fleeting day of September!
How audacious it is to advance in stately manner before the blue-tit fluttering in the shrubs that have long lost their leaves, like a queen with the spring’s greeting on her lips;
to bloom with steadfast hope that, parted from the cold flower-bed, she may be the last to cling, intoxicated, to a young hostess’s breast.”
—Afanasi Fet (1820–1892)