Boost logo

Boost :

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


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