Boost logo

Boost :

Subject: Re: [boost] [GSoC] Request for Feedback on Boost.Bloom Filter Project
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-06-26 12:55:17


Arash Partow wrote:
> Phil Endecott wrote:
> > Sorry Arash but I don't understand your reply; what exactly
> > is correct?
>
> My point was that you are correct, the "and" does not provide anything of
> value. Only "or" and "xor" are practical for non-counting bloom filters.

Well no, that's not what I said.

For clarity, I believe that:

1. Bitwise OR of two bloom filters achieves the set union without any
side effects.

2. Bitwise AND of two bloom filters achieves the set intersection, but
it will introduce additional false positives, which may or may not be
acceptable since they are already inherent in bloom filters.

3. Bitwise XOR of two bloom filters achieves something like the set
symetric difference, but will introduce false negatives, which probably
are not acceptable because bloom filters do not otherwise suffer from them.

> I'm not sure what you mean by overlapping hashes

I simply mean the case where two distinct values have the same hash for
some of the hash functions.

Regards, Phil.


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