Re: [boost] Request interest in Bloom filters

Subject: Re: [boost] Request interest in Bloom filters
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-03-23 09:16:15

vicente.botet wrote:
> I need for my application bloom filters. Do you know of a good boostified 
> generic implementation?
> Is there any interest in such a generic bloom filters library in Boost?

Hi Vicente,

I have a simple generic Bloom filter here:

     http://svn.chezphil.org/libpbe/trunk/include/bloom_filter.hh

This is GPL licensed but I'd be happy to change that to the Boost 
license if someone wanted to make a Boost library using it.

After writing this code I eventually decided to use a different method, 
so I'm not currently using this code anywhere.

The code is very straightforward.  I spent much longer learning the 
theory of Bloom filters than I did implementing it.  Unfortunately I've 
now forgotten much of the theory and all that is left is the code...

What's not included is hash functions; you have to supply these as a 
template parameter.  I used Boost.CRC and the hash function from std:: 
unordered containers.  I seem to have lost the example code that did 
this.  One general problem with this approach is to find enough 
independent hash functions.  Say I'm storing strings and I need four 
hash functions; the temptation is to have one function and to compute 
e.g. f(x), f("123"+x), f("456"+x), f("789"+x).  These will give 
different answers and may look like they're independent functions, but 
it's not really certain how independent they are.

Cheers,  Phil.