Jaccard Similarity

The Jaccard similarity measures the fraction of shared elements between set. In particular, given set $A$ and $B$ , the Jaccard similarity between them is defined as

J(A, B) = \frac{|A \cap B|}{|A \cup B|}

The naive calculation of $J(A, B)$ has time complexity $O(|A \cup B|)$ by scanning all elements in the two sets once. Here we discuss how randomization might save time.

Lemma One

If we select an item $x$ uniformly at random from $|A \cup B|$ , then $\Pr[x \in A \cap B] = \frac{|A \cap B|}{|A \cup B|}$ .

Define the random variable

X = \begin{cases} 1, \ if \ x \in \ A \cap B \\ 0, \ otherwise \end{cases}

Then we see that $X$ is an unbiased estimator of $J(A, B)$ , i.e., $E[X] = J(A, B)$ .

Suppose that we have a sequence of i.i.d. copies of $X$ , denoted $X_1, X_2, ..., X_k$ , then the average $\mu = \frac{1}{k} \sum_{i = 1}^k X_i$ is also an unbiased estimator of $J(A, B)$ . Moreover, by law of large number, $\mu \rightarrow J(A, B)$ as $k \rightarrow \infty$ . The problem is, how many $X_i$ 's are enough.

The answer depends on a few factors:

Whether the value of the required error is relative to $J(A, B)$ or independent to $J(A, B)$ .
What is the tolerance of failure probability.

In the following discussion we consider only the case of finding an estimator $\mu$ such that $J(A, B) \in [\mu \pm \epsilon]$ with probability at least $1 - \delta$ , where both $\epsilon$ and $\delta$ are given parameters. Then the convergence behavior with respect to the number of samples $k$ can be captured by Hoeffding inequality:

\Pr[ |\mu - J(A, B)| \ge \epsilon] \le 2\exp \left( -\frac{2\epsilon^2}{k} \right) = \delta

Solving the equation gives

k = \frac{2}{\epsilon^2}\log \frac{2}{\delta}

Or equivalent, when we interpret $\epsilon$ as the width of confidence interval,

\epsilon = \sqrt \frac{\log \frac{2}{\delta} }{k}

which has order $O(\sqrt \frac{1}{k})$ .