Re: [boost] Re quest interest in Bloom filters

Subject: Re: [boost] Re quest interest in Bloom filters
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-03-23 12:15:01

Vicente Botet Escriba wrote:
> Phil Endecott-48 wrote:
>> 
>> 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

>> I seem to have lost the example code

Now found and checked in here:

     http://svn.chezphil.org/libpbe/trunk/examples/spellcheck.cc

> The hard part (the hash functions) is left out quite elegantly. I was
> thinking about defining some hash traits wich will allow the user to set the
> hash functions in a independent way. Something like
>
> template <template T, size_t N> struct hash_traits;
>
> template <> hash_traits<SpecificUserType,0> {
>     static unsigned hash(T& value) {
>         // specific code
>     }
> }
>
> BTW, besides the tr1::hash function, are there other hash generic functions
> in Boost?

You can use Boost.CRC.  What sort of key do you have?  I once did some 
investigation of hash functions for strings for use with unordered 
containers; I was considering using a degenerate hash that only looks 
at the first N characters.

Something I didn't mention before is that if you need, say, 10-bit hash 
values then a 32-bit CRC could give you three of them.  In this case 
your hash_traits would presumably compute the same CRC three times and 
extract different portions each time, which is not ideal.

> I would need also the union and intersection functions. I'm wondering if
> replacing the tr1::array by a boost::dynamic_bitset should make eassier
> this.

Well it's not exactly difficult with the array.  I've never used 
dynamic_bitset and being dynamic is not a requirement here.  I was 
concerned (as normal) about getting a fast implementation and the 
simple bit manipulation in my code is probably about as fast as you can get.

Cheers,  Phil.