Re: [bloom] Peer Review Conclusion

From: Kostas Savvidis (kotika98_at_[hidden])
Date: 2025-05-30 16:12:14

> 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.

K