Bloom Filters

SlashDot recently posted an article about LOAF. LOAF is an interesting idea. The site is worth looking at for it’s own sake. However, what I found really interesting was the tidbit of computer science behind LOAF called a Bloom Filter.

A Bloom Filter uses multiple hash functions and a large bit array to represent a set. The set cannot be reconstructed from the Bloom Filter. There is a small possibility that the Bloom Filter will return a false positive but a false negative is impossible.

Here are some links with more information:

The original article on Bloom filters:

Communications of the ACM
Volume 13 , Issue 7 (July 1970)
Pages: 422 – 426
Year of Publication: 1970

This article is available in the ACM digital library.

Leave a Reply

Your email address will not be published. Required fields are marked *