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.

 

Technorati Tags: C#, Very Large Data Structures (VLDS)