Boost logo

Boost :

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:
> 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:

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


View this message in context:
Sent from the Boost - Dev mailing list archive at

Boost list run by bdawes at, gregod at, cpdaniel at, john at