# Number of non-zero elements in intersection of two bloom filters

Let us assume I use bloom filters of size $$m$$ bits with $$k$$ hash functions.

Now I have two set $$X$$ and $$Y$$. Let $$B(X)$$ be bloom filter of the set $$X$$. In general I know that $$B(X\cup Y)= B(X) \lor B(Y)$$. Let us assume that $$|X|=n, |Y|=m, |X\cap Y|=l$$.

So I can use formula from wiki for math expectation for number of non zero element in $$B(X\cup Y)$$.

Howewver it is not true that $$B(X\cap Y)= B(X) \land B(Y)$$. Can I theoretically compute how many non-zero elements $$B(X) \land B(Y)$$ should have?

• What's the motivation for caring about the number of non-zero elements of $B(x) \land B(Y)$?
– D.W.
Sep 7 at 15:51
• I want to use it to estimate the size of $X\cap Y$. Sep 7 at 21:59

Focus on a particular bit position, say the $$i$$th bit position. Let $$E$$ be the event that this bit is set in $$B(X) \land B(Y)$$. Now all you need to do is to estimate $$\Pr[E]$$. Then the expected number of non-zero elements in $$B(X) \land B(Y)$$ will be $$m\Pr[E]$$.

To help us estimate $$\Pr[E]$$, let's break this down into cases. Define $$S=X \setminus Y$$, $$T=Y \setminus X$$, $$U=X \cap Y$$. Also define the event $$E_S$$ to represent that this bit is set in $$B(S)$$, $$E_T$$ that it is set in $$B(T)$$, and $$E_U$$ that it is set in $$B(U)$$.

It will be easier to estimate $$\Pr[\neg E]$$. Note that

$$\Pr[\neg E] = \Pr[\neg E_U \land \neg (E_S \land E_T)] = \Pr[\neg E_U] \cdot \Pr[\neg (E_S \land E_T)].$$

Now

$$\Pr[\neg E_U] = (1 - \frac{1}{m})^{kn_U} \approx \exp \{-kn_U/m\},$$

where $$l=|X \cap Y|=|U|$$. Also

\begin{align*} \Pr[\neg E_S] &= (1 - \frac{1}{m})^{k n_S} \approx \exp\{k n_S/m\}\\ \Pr[\neg E_T] &\approx \exp\{kn_T/m\} \end{align*}

so we have

$$\Pr[E_S \land E_T] = \Pr[E_S] \cdot \Pr[E_T] \approx (1 - \exp\{k n_S/m\}) (1 - \exp\{kn_T/m\}).$$

It follows that

$$\Pr[\neg E] \approx \exp\{-kn_U/m\} \cdot [1 - (1 - \exp\{k n_S/m\}) (1 - \exp\{kn_T/m\})],$$

and

$$\Pr[E] \approx 1 - \exp\{-kn_U/m\} \cdot [1 - (1 - \exp\{k n_S/m\}) (1 - \exp\{kn_T/m\})].$$

Multiply by $$m$$, and that is your desired estimate for the number of non-zero elements in $$B(X) \land B(Y)$$.

If you want to express this estimate in terms of the sizes $$|X|$$, $$|Y|$$, and $$|X \cap Y|$$, note that $$n_U=|X\cap Y|$$, $$n_S=|X|-|X\cap Y|$$, and $$n_T=|Y| - |X\cap Y|$$, and plug into the formula above.

If you want to estimate the size of $$|X \cap Y|$$ from the number of non-zero elements in $$B(X) \land B(Y)$$, you just need to invert the above equation. You could use binary search on $$n_U$$ to find the value of $$n_U$$ that gives the closest match between expected number of bits set and actual bits set.