0
$\begingroup$
  • 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)
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Jan 30, 2022 at 23:58

1 Answer 1

1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.