Friday, June 15, 2007

Bloom Filter

Very fascinating reading.

"The Bloom filter, conceived by Burton H. 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 positives are 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." -- Wikipedia

Also you can find a good examples in C# by Jim Mischel

Some of my own testing for 400,000 items insert requires 2,104,541 bits array. False positives for this large number of tests is kept at 2.4% which is amazing.

You can find out these numbers with Bloom Filter Calculator by Panagiotis (Pete) Manolios.



Sean Nieuwoudt said...


Im looking into bloom filters myself, could you perhaps post your examples of your work?


petar said...