From: Dave Thomas <Dave@...>
Date: 2001-01-03T03:54:36+09:00
Subject: [ruby-talk:8531] Re: speedup of anagram finder

Hugh Sasse Staff Elec Eng <hgs@dmu.ac.uk> writes:

> > How about going statistical? Anyone fancy writing a Bloom filter based 
> 
> What is a Bloom filter?  A pointer to the info will do, of course, but
> this is phrased as if I should already know about it, so I thought I'd
> better ask promptly! :-)

A very cool and trivially simple algorithm for determining with some
statistical probability if a member is in some set, where the storage 
of the set is far less than the storage required for all the members.

   http://www.flipcode.com/tutorials/tut_bloomfilter.shtml

I first used it in a spelling checker in 1980, but it's been around
much longer than that. Web caches such as Squid often use Bloom
filters to look for potential hits, and they can be used to implement
whitelists and blacklists.

It's worth trying to find the original ACM article, because the link
above seems to use too many hashes: I seem to remember that you get an 
increasing number of false positives if you increase the number of
bits you set per member of the set, but it was a long, long time ago.


Regards


Dave