Re: [boost] Re quest interest in Bloom filters

Subject: Re: [boost] Re quest interest in Bloom filters
From: Vicente Botet Escriba (vicente.botet_at_[hidden])
Date: 2009-03-23 11:16:52

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
> 
> 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.
> 
> 
> 
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
> 
> 

Hi,
thanks for the pointer.

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?

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.

Best,
Vicente
-- 
View this message in context: http://www.nabble.com/Request-interest-in-Bloom-filters-tp22651050p22662216.html
Sent from the Boost - Dev mailing list archive at Nabble.com.