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

Question

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?

Answer 1

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.