Deduplication › Worked Example: Exact and Jaccard Deduplication

Let us work through a small example to make these concepts concrete. Consider a tiny corpus of five documents:

• D1: "The quick brown fox jumps over the lazy dog"
• D2: "The quick brown fox jumps over the lazy dog" (exact copy of D1)
• D3: "A quick brown fox leaped over the sleeping dog" (paraphrase of D1)
• D4: "Machine learning requires large amounts of training data"
• D5: "Machine learning requires large amounts of labeled data" (minor variation of D4)

Step 1: Exact deduplication. We hash each document after normalization:

• $h(D1) = h(D2)$ because the strings are identical after normalization
• $h(D3)$, $h(D4)$, $h(D5)$ are all different from each other and from $h(D1)$

Result: D2 is removed. We keep D1, D3, D4, D5.

Step 2: Near-duplicate detection with $k=5$ character shingles. The 5-shingles for D1 ("the quick brown fox...") and D3 ("a quick brown fox...") share many substrings like "quick", "uick ", "ick b", "ck br", etc. The documents differ primarily in the first character ("the " vs "a qu") and in a few words later on, but most of the character content is shared. Their Jaccard similarity over 5-shingles is noticeably above zero.

For D4 and D5, the only content difference is "training" versus "labeled". Both words have different character sequences, but the surrounding words ("large amounts of ", " data") are identical, and those surrounding characters contribute many shared shingles. The net effect is high Jaccard similarity because the differing segment is short relative to the shared segments.

With threshold $\tau = 0.5$, we would remove D3 (similar to D1) and D5 (similar to D4), leaving D1 and D4 as the deduplicated corpus. The exact cutoffs depend on the actual Jaccard values, which depend on document length and the specific character content. Shorter documents are more sensitive to small changes because the differing characters represent a larger fraction of the total content.