Re: [boost] [GSoC] Request for Feedback on Boost.Bloom Filter Project

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.