# hamming distance of bloom filters

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?

• 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. – Yuval Filmus Jun 7 '17 at 19:55

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.