Boost logo

Boost :

Subject: Re: [boost] Boost.Bloom_filter now in Sandbox (WAS Re: Interest in a Bloom Filter?)
From: Vicente Botet Escriba (vicente.botet_at_[hidden])
Date: 2009-06-09 09:49:35


Dean Michael Berris wrote:
>
> Just an update -- as of Sandbox revision 53772, I've addressed some of
> the issues below:
>
> On Tue, Jun 9, 2009 at 12:52 PM, Dean Michael
> Berris<mikhailberis_at_[hidden]> wrote:
>> On Tue, Jun 9, 2009 at 4:36 AM, Joaquin M Lopez Munoz<joaquin_at_[hidden]>
>> wrote:
>>>
>>> So you can still get a lot of feedback till the design
>>> reaches a mature state. IMHO there're plenty of
>>> opportunities for improvement, here are a handful of
>>> observations in no particular order:
>>>
>
>>> 3. Have you considered the possibility to let
>>> the user specify M and K at constuction time rather
>>> than compile tiem and the pros and cons of both
>>> approaches?
>>
>> Yes, I have but I've put a premium at type safety and putting M and K
>> as part of the type instead of being a runtime value. The reasons are:
>>
>> 1. Specifying a static M allows the use of the standard bitset instead
>> of Boost's dynamic_bitset.
>> 2. A static K allows for enforcing the number of hash functions at
>> compile time instead of at runtime.
>> 3. Since M and K are not variable and are part of the type, it makes
>> little sense for me to have either of them set at construction time.
>>
>> One thing I might be amenable to is a static K and a runtime M, but
>> that makes the hash functions unable to determine statically the
>> bounds of the bitset (M). I can change the concept for the hash
>> function, but the simplicity of size_t(Input) just makes it easier for
>> users I think.
>
> I thought about it a little more and I don't think I like the idea of
> a separate static and dynamic bloom_filter. If there are more reasons
> to allow for dynamically growing bloom filters, then I might support
> this.
>

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;

Dean Michael Berris wrote:
>
>
>>> 7. bloom_filters are not currently testable for
>>> equality.
>>
>> You're correct. I'll add this soon.
>>
>
> Done, but I've run into the issue of not being able to compare
> boost::function objects of the same type -- for some reason this has
> been disabled in Boost Trunk.
>
>

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.

Dean Michael Berris wrote:
>
>
>>> 8. bloom_filters are not currently serializable.
>>
>> True. I might need to have a file 'boost/bloom_filter/serialize.hpp'
>> to add serializability non-intrusively.
>>
>
> This should come later... I still need to look into whether
> serialization should only be done for the bitset state rather than the
> whole type. I say this because up to now I don't think there's a way
> of serializing boost::function objects and deserializing them
> effectively either.
>
>

If hash functions make part of the bloom_filter type there is no issue, only
the data must be serialized.

HTH,
Vicente

-- 
View this message in context: http://www.nabble.com/Boost.Bloom_filter-now-in-Sandbox-%28WAS-Re%3A-Interest-in-a-Bloom-Filter-%29-tp23922689p23943240.html
Sent from the Boost - Dev mailing list archive at Nabble.com.

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk