3
$\begingroup$

In the introduction of Distance-Sensitive Bloom Filters the authors state:

The relative Hamming distance between two Bloom filters (of the same size, and created with the same hash functions) can be used as a measure of the similarity of the underlying sets.

This statement is followed by a reference to another paper, which could not clarify this statement for me.

Question: What is the precise relation between the hamming distance of two bloom filters and the similarity of the corresponding sets?

$\endgroup$
  • 1
    $\begingroup$ They don't claim that there is any relation to other notions of similarly (though I'm sure there is some), only that relative Hamming distance can be used as a measure of similarity. In other words, they define similarity as having a small Hamming distance. $\endgroup$ – Yuval Filmus Jun 7 '17 at 19:55
1
$\begingroup$

Let $S,T$ be two sets of size $n$. Suppose we hash each to a $m$-bit Bloom filter, using $k$ hash functions; let $x_S$ be the $m$-bit vector corresponding to $S$, and $x_T$ the $m$-bit vector corresponding to $T$.

If $S,T$ agree in a $p$ fraction of entries (i.e., $|S \cap T|=pn$), then the expected value of the Hamming distance between these two bit-vectors is

$$\mathbb{E}[d(x_S,x_T)] \approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

This gives a relation between the similarity of the two sets (in terms of the number of elements they have in common) and the Hamming distance between their Bloom filters. In particular: the greater their similarity, the smaller the (expected) Hamming distance between their Bloom filters.


Derivation and details

Where did I get this expression for the expected value of the Hamming distance from from? Well, consider the $i$th bit of $x_S$. The probability that this is 0 is

$$\Pr[x_S[i]=0] = \left( 1 - {1 \over m} \right)^{kn}.$$

For the corresponding bit of $x_T$, the probability it is 1 is

$$\Pr[x_T[i]=1] = 1 - \left( 1 - {1 \over m} \right)^{kn}.$$

How about the conjunction of these two events, i.e., that $x_S[i]=0$ and $x_T[i]=1$? We can't just multiply the two probabilities, because the two events aren't independent: the $pn$ elements in $S \cap T$ will certainly hash to the same place. However, we can take that into account by expressing the probability as

$$\Pr[x_S[i]=0 \land x_T[i]=1] = q_1 \times q_2 \times q_3$$

where $q_1$ is the probability that none of the elements of $S \setminus T$ hash to position $i$ (i.e., $\Pr[x_{S \setminus T}[i]=0]$); $q_2$ is the probability that none of the elements of $S \cap T$ hash to position $i$ (i.e., $\Pr[x_{S \cap T}[i]=0]$); and $q_3$ is the probability that at least one of the elements of $T \setminus S$ hashes to position $i$ (i.e., $\Pr[x_{T \setminus S}[i]=1]$). Each of these can be computed as

$$\begin{align*} q_1 &= \left(1 - {1 \over m}\right)^{k \cdot |S \setminus T|} = \left(1 - {1 \over m}\right)^{k(1-p)n}\\ q_2 &= \left(1 - {1 \over m}\right)^{k \cdot |S \cap T|} = \left(1 - {1 \over m}\right)^{kpn}\\ q_3 &= 1 - \left(1 - {1 \over m}\right)^{k \cdot |T \setminus S|} = 1 - \left(1 - {1 \over m}\right)^{k(1-p)n}. \end{align*}$$

Therefore, multiplying these quantities, we find that

$$\Pr[x_S[i]=0 \land x_T[i]=1] = \left(1 - {1 \over m}\right)^{kn} \times \left(1 - \left(1 - {1 \over m}\right)^{k(1-p)n} \right).$$

Using the approximation $(1 - 1/m)^t \approx e^{-t/m}$, we see that

$$\Pr[x_S[i]=0 \land x_T[i]=1] \approx \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

Now by symmetry,

$$\begin{align*} \Pr[x_S[i] \ne x_T[i]] &= \Pr[x_S[i]=0 \land x_T[i]=1] + \Pr[x_S[i]=1 \land x_T[i]=0]\\ &\approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}). \end{align*}$$

Finally, linearity of expectation tells us that the expected Hamming distance between $x_S$ and $x_T$ is $m$ times the above quantity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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