MinHash › Jaccard Similarity

Before building MinHash, you need to understand what similarity measure it estimates: Jaccard similarity. This measure has a long history in ecology and information retrieval, and its properties make it particularly well suited for detecting near-duplicate documents.

The Jaccard similarity between two sets $A$ and $B$ measures overlap as a fraction of union:

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

where:

• $|A \cap B|$: the number of elements appearing in both $A$ and $B$
• $|A \cup B|$: the number of distinct elements appearing in either $A$ or $B$

Jaccard similarity ranges from 0 to 1. A score of 0 means the sets share no elements at all. A score of 1 means the sets are identical, containing exactly the same elements. For text documents, you represent each document as a set of overlapping substrings (called shingles or n-grams), then compute Jaccard similarity over those sets.

The intuition behind using Jaccard for documents is straightforward. If two documents are near-duplicates, they share most of their substrings, so the intersection of their shingle sets is nearly as large as the union. If two documents are completely unrelated, they share almost none of their characteristic phrases, so the intersection is tiny relative to the union. The ratio captures exactly how much of the content is shared.

Cosine similarity is another popular choice for comparing text representations, but it has different properties that make it less ideal for near-duplicate detection. Cosine similarity measures the angle between two vectors in a shared feature space, which makes it insensitive to magnitude differences. Two documents can have high cosine similarity even if one is much longer than the other, as long as their term frequencies are proportionally similar. For duplicate detection, you typically want a measure that penalizes documents that share only a small fraction of their content, and Jaccard does this naturally through the union in the denominator.

Jaccard is also naturally defined over sets, which maps cleanly onto the shingling representation of documents. There is no need to build a vocabulary or construct term-frequency vectors; you just extract substrings and compare sets. This simplicity is computationally important when processing billions of documents.

Consider these two sentences:

• Document A: "the cat sat on the mat"
• Document B: "the cat sat on a mat"

If you extract 3-word shingles (overlapping windows of 3 consecutive words):

Document A generates: {the cat sat, cat sat on, sat on the, on the mat}

Document B generates: {the cat sat, cat sat on, sat on a, on a mat}

The intersection contains 2 shingles: {the cat sat, cat sat on}. The union contains 6 distinct shingles. Therefore:

$$J(A, B) = \frac{2}{6} \approx 0.333$$

Even though these documents differ by only one word ("the" vs "a"), their Jaccard similarity over 3-word shingles is only 0.33. This is because each changed word affects multiple overlapping shingles. Shorter shingles capture changes more coarsely; longer shingles are more sensitive to local edits. Choosing the right shingle size is one of the key design decisions in a MinHash pipeline.

Jaccard distance, defined as $d(A, B) = 1 - J(A, B)$, is a valid metric: it is symmetric, non-negative, zero only for identical sets, and satisfies the triangle inequality. This metric property has useful consequences. It means you can use Jaccard distance in metric data structures, and it provides theoretical guarantees for clustering algorithms based on Jaccard distance. MinHash, which approximates Jaccard similarity, inherits these properties approximately.