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:
- Bloom Filters – the math
- A little Bloom Filter Theory
- Network Applications of Bloom Filters: A Survey
- perl.com: Using Bloom Filters
The original article on Bloom filters:
Communications of the ACM
Volume 13 , Issue 7 (July 1970)
Pages: 422 – 426
Year of Publication: 1970
ISSN:0001-0782
This article is available in the ACM digital library.
