Wednesday, May 11, 2011

I've Just Learned About Bloom Filter

Although the algorithm was invented at about the same time that I was born, I've just understood how Bloom filter works today :-)

From Wikipedia page, the Bloom filter "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."

Here's a discussion about a 22-line Python implementation of the filter.

No comments: