Deduplication › Near-Duplicate Detection with Jaccard Similarity

Most real-world duplication is not exact. Articles get paraphrased, headlines change, paragraphs get reordered, and syndication services add or remove bylines and footers. To catch these near-duplicates, you need a similarity measure that tolerates small differences.

The standard approach uses Jaccard similarity over sets of character n-grams. The appeal of this approach is its simplicity and its direct connection to what we intuitively mean by "similar content": two documents that share most of their character sequences are probably expressing similar information, even if the exact wording differs.

Given a document $d$, you convert it to a set of overlapping character sequences of length $k$, called k-shingles or k-grams. For example, with $k = 5$, the string "the cat sat" produces shingles: {"the c", "he ca", "e cat", " cat ", "cat s", "at sa", "t sat"}.

Formally, the shingle set of document $d$ with shingle size $k$ is defined as all substrings of length $k$ that appear in $d$:

$$S_k(d) = \{d[i : i+k] \mid 0 \leq i \leq |d| - k\}$$

where:

• $d$: the document as a string of characters
• $k$: the shingle length (number of characters per shingle)
• $d[i : i+k]$: the substring of $d$ starting at position $i$ with length $k$
• $|d|$: the total length of the document in characters
• $S_k(d)$: the resulting set of unique k-character substrings (a set, not a multiset, so duplicates within one document are collapsed)

The choice of character-level shingles rather than word-level n-grams is deliberate. Word-level shingles are sensitive to tokenization choices and vocabulary differences across languages. Character-level shingles are language-agnostic and naturally capture morphological variations (for example, "running" and "runner" share most of their characters). They also gracefully handle misspellings and OCR errors, where individual words may differ but most character sequences remain shared.

Why convert a document to a set rather than a sequence? Because sets abstract away the positions of shingles and focus entirely on their presence or absence. Two documents that express the same ideas in different paragraph orders would have very different sequence representations, but highly overlapping set representations. For deduplication, we care about content overlap, not structural alignment, so sets are the right data model.

Common choices for $k$ range from 5 to 10. Shorter shingles ($k=3$ or $k=4$) are too common across unrelated documents, producing many false positives: every document in English contains the shingle "the" repeatedly, so short shingles create apparent similarity between unrelated texts. Longer shingles ($k=15$ or $k=20$) become too document-specific, missing near-duplicates that differ in small ways. The sweet spot at $k=5$ to $k=8$ produces shingles specific enough to carry content signal but common enough to appear across near-duplicate pairs even when wording differs slightly.

The key insight behind Jaccard similarity is that two documents sharing most of their content will share most of their shingles. Representing documents as shingle sets lets us quantify how much their content overlaps. Given two documents represented as shingle sets $A$ and $B$, Jaccard similarity measures the fraction of shingles they share:

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

where:

• $A$: the shingle set of the first document
• $B$: the shingle set of the second document
• $|A \cap B|$: the number of shingles that appear in both documents (the intersection)
• $|A \cup B|$: the total number of distinct shingles across both documents (the union)
• $J(A, B)$: the similarity score, ranging from 0 (no shared shingles) to 1 (identical shingle sets)

The denominator normalizes by the union rather than by either set's size alone, which is important. If you normalize by the smaller set's size, a short document that is entirely contained within a long document would receive a similarity of 1.0, even if the long document has substantial additional content. Jaccard's union normalization penalizes both asymmetry and total mismatch: documents are judged similar only when their shared content is large relative to everything both documents contain.

To build intuition, consider two documents $A$ and $B$ where $|A \cap B| = 40$ and $|A \cup B| = 50$. The Jaccard similarity is $40/50 = 0.8$, meaning 80% of all shingles appearing in either document appear in both. This suggests the documents share most of their content. If instead $|A \cap B| = 10$ and $|A \cup B| = 100$, the Jaccard similarity drops to $0.1$, indicating the documents share only 10% of their combined vocabulary. These interpretations are intuitive and directly meaningful for deduplication decisions.

Documents with Jaccard similarity above some threshold $\tau$ (typically 0.7 to 0.8 for deduplication) are treated as near-duplicates, and one copy is discarded.

The problem with computing Jaccard similarity directly is the cost. For a corpus of $N$ documents, a naive pairwise comparison requires $O(N^2)$ similarity computations. At 100 million documents, that is $5 \times 10^{15}$ comparisons. Even at one million comparisons per second, completing the computation would take more than 150 years. This is where MinHash comes in: a locality-sensitive hashing technique that estimates Jaccard similarity efficiently without comparing all pairs directly. We cover MinHash in full detail in the next chapter, but we introduce its key ideas in the Deduplication at Scale section below.