Boost logo

Boost :

Subject: Re: [boost] Boost.Bloom_filter now in Sandbox (WAS Re: Interest in a Bloom Filter?)
From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2009-06-10 05:26:27

On Tue, Jun 9, 2009 at 11:57 PM, Dean Michael
Berris<mikhailberis_at_[hidden]> wrote:
> On Tue, Jun 9, 2009 at 9:49 PM, Vicente Botet
> Escriba<vicente.botet_at_[hidden]> wrote:
>> Two bloom_filters with different hash functions are not comparable.
>> Don't you think that the hash functions make part of the bloom_filter type?
>>    bloom_filter<M, hash_1, ... hash_k>bf;
> Thinking about it a little more, yes this makes sense. However,
> pending the formalization of variadic templates, I'm leaning towards
> supporting Fusion sequences in the collection of hash functions:
>    bloom_filter<Input, M, Sequence> bf;
> This way I can deduce K from size<Sequence> and maybe even derive the
> bloom_filter linearly from the Sequence elements (to optimize the
> storage, using the compressed_pair trick). I'm still mulling it around
> in my head, and will be trying to implement this in the morning (PH
> time).
> My only worry with this is that I'd have to define the Concept for
> hash function types. It shouldn't be too hard especially if I'll build
> upon the Boost.Hash concepts (if they're applicable).

This has also been addressed in the version that's in revision 53785
of the Boost Sandbox. :-)

>> If hash functions make part of the bloom_filter type there is no issue. No
>> need to compare the hash functions at run-time. The compiler will do it for
>> you.
> Yup, this is true. Now I just have to implement it using Boost.Fusion
> -- this I'm worried about because this somewhat makes the bloom_filter
> implementation (and usage) a little more complex than I'd like, but if
> the requirements dictate it then there would be less reasons for me to
> avoid it. ;-)

And my worries were misplaced. :-) The implementation seems cleaner
now IMO using Boost.Fusion internally. Fusion saves my day again. :-D

>> If hash functions make part of the bloom_filter type there is no issue, only
>> the data must be serialized.
> You're correct here. Now it's just a matter of me implementing it then. :-)

And this is already done too. :-)

Thanks for the insights! :-D

Dean Michael Berris | Software Engineer, Friendster, Inc. | | | |

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