Re: [bloom] Peer Review Conclusion

From: Peter Dimov (pdimov_at_[hidden])
Date: 2025-05-30 16:27:15

Kostas Savvidis wrote:
> > On 29 May 2025, at 20:37, Joaquin M López Muñoz via Boost
> <boost_at_[hidden]> wrote:
> >
> > given two sequences of hash values hi and gi, we're not interested in
> > internal correlation of either hi or gi, but cross correlation between
> > the two sequences.
> 
> I am actually not sure which is more important for a Bloom filter,
> autocorrelation or cross-correlation.
> 
> What is known is that the cross-correlation between two sequences in any
> MCG or LCG ( x' = a * x mod k)  is even worse than the autocorrelation.
>  It goes like this: if in the first bucket h1 = 2*g1, then hi=2*gi for all i or
> buckets. This is independent of a and k. Same if you replace the "2" with "3"
> etc.
> Effectively there is 100% correletion between buckets. One cannot fix that
> even with a better multiplier.

It's not clear to me why this would be a problem, but if it is, it can be fixed
by using an LCG (a*x+b) instead of an MCG (a*x).