Bloom Filters

“The basic bloom filter supports two operations: test and add.

Test is used to check whether a given element is in the set or not. If it returns:

– false then the element is definitely not in the set.
– true then the element is probably in the set. The false positive rate is a function of the bloom filter’s size and the number and independence of the hash functions used.

Add simply adds an element to the set. Removal is impossible without introducing false negatives, but extensions to the bloom filter are possible that allow removal e.g. counting filters…”

http://www.jasondavies.com/bloomfilter/

Advertisements