Re: [boost] Boost.Bloom_filter now in Sandbox (WAS Re: Interest in a Bloom Filter?)

Subject: Re: [boost] Boost.Bloom_filter now in Sandbox (WAS Re: Interest in a Bloom Filter?)
From: Manuel Fiorelli (manuel.fiorelli_at_[hidden])
Date: 2009-06-09 15:35:34

2009/6/9 Dean Michael Berris <mikhailberis_at_[hidden]>:
> Hi Manuel,
>
> On Tue, Jun 9, 2009 at 8:45 PM, Manuel
> Fiorelli<manuel.fiorelli_at_[hidden]> wrote:
>> About the implementation:
>> If I understand your implementation, you do something like that:
>> given a value V,
>> you compute a number X (say the digest of V),
>> then you compute K different values applying the transformation (X +
>> offset) mod(M)
>>
>
> Right. This naive filter will almost always create K consecutive
> indexes (or results) from the hash functions.

Well, the K hash functions should be independent, but actually the
default functions are highly correlated. I suspect that a more
sophisticated approach should be taken. Wikipedia suggests some
techniques and some references.

Manuel Fiorelli