1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your detailed answer! $\endgroup$ Sep 8, 2023 at 9:53

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.