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.

 

2 comments:

Sean Nieuwoudt said...

Hi,

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

Regards,
Sean

petar said...

http://www.devsource.com/c/a/Languages/Bloom-Filters-in-C/