# Is the equality of Bloom filters analogous to set equivalence?

• I have two multisets $$A$$, $$B$$ where $$A \subseteq B$$.
• Using these two sets, we construct two Bloom filters $$BF(A), BF(B)$$; both using bitsets of size $$n$$ with the same $$k$$ hash functions.

What's the probability that:

$$A \not\equiv B$$ but $$BF(A) = BF(B)$$

Notes:

• Since $$A$$ and $$B$$ are multisets, they might have duplicate elements.
• However, duplications should not affect set equaivalence or subset relation. Due to lack of notation (on my side) please assume deduplication when checking for subsets or equivalence.
• By Bloom filter equality, I mean the bitsets being equal.
• I think we could assume hash functions are random and are independent of the elements of the sets.
• If needed, Jaccard index (ratio of intersection over union as an indicator of set similarity) could be approximated as $$J(A,B) = \frac{|A|}{|B|}$$ (or via MinHash)
• What have you tried? Can you analyze any special case? For instance, if $|A|=|B|=1$, can you figure out the answer? What if $|A|=1$ but $B$ is arbitrary? Do you want an exact answer even if the formula is a complex sum, or do you want an approximate answer that shows the asymptotics, or what?
– D.W.
Jan 30, 2022 at 23:58

It is possible to find an upper bound on the probability of a collision in the fingerprint. Suppose the Bloom filter uses $$k$$ hash functions and maps into a bit array of size $$m$$.

The case $$k=1$$ is much easier to analyze explicitly, so I'll start with that case.

If $$A\ne B$$, there must be some element that is in $$A$$ but not $$B$$, let's say $$a$$. $$a$$ must hash to some bit of the array. With probability $$(1-1/m)^{|B|}$$, none of the elements of $$B$$ map to this bit position, and in this case, we necessarily have $$BF(A)\ne BF(B)$$.

So, if $$A \ne B$$, the probability that $$BF(A)=BF(B)$$ is at most $$1 - (1-1/m)^{|B|}$$. When $$|B|$$ is small compared to $$m$$, this is roughly $$|B|/m$$.

The calculations get messier when $$k>1$$. If you're satisfied with an approximate upper bound, you can use the fact that when $$k \ll \sqrt{m}$$, $$a$$ will typically hash to $$k$$ different bits ($$k$$ different positions in the array). The probability that at least one of the elements of $$B$$ maps to a particular bit is roughly $$|B|k/m$$, assuming $$|B| \ll m/k$$ (following similar reasoning to that above). So, the probability that all of those $$k$$ bits are mapped to by some element of $$B$$ is roughly $$(|B|k/m)^k$$.

So, if $$A \ne B$$, the probability that $$BF(A)=BF(B)$$ is at most about $$(|B|k/m)^k$$, under the conditions that $$|B| \ll m/k$$ and $$k \ll \sqrt{m}$$.

• Thank you this gives me enough direction of thought to address the cases where $k > 1$. Jan 31, 2022 at 7:27