Given two sets, S1 and S2, and their corresponding bloom filters, BF1 and BF2, is there a way to prove that |BF1 ∩ BF2|/|BF1 ∪ BF2| = |S1 ∩ S2|/|S1 ∪ S2| (we can assume both bloom filters are generated using the same set of hash functions)? If not, is there a way to approximate one given the other?

  • $\begingroup$ @D.W. I think you may have misread the question: both bloom filters being generated using the same hash functions is an assumption, not a question. Given this assumption, I am asking whether or not the given ratios are equal (I suppose I am looking for a proof of this statement and have edited the question accordingly). $\endgroup$ – Chris H. Mar 6 '17 at 21:25
  • $\begingroup$ OK. Thanks for the edit! Next questions: (1) What does $|BF|$ mean? Can you define that notation? Is it the number of bits set in the bloom filter $BF$? (2) Have you tried to prove or disprove this? Have you worked through some small examples? I think if you work through some very small examples (let's say, where $|S|_1=|S|_2=1$) you should quickly be able to answer your first question.... $\endgroup$ – D.W. Mar 6 '17 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.