Day 52: Plagiarism Detection

System Design with Data Structures & Algorithms ~10 min read 60 min hands-on

Welcome back, architects and engineers! Today, we're diving deep into a problem that quietly underpins countless systems, from protecting academic integrity to safeguarding intellectual property in vast codebases: large-scale plagiarism and similarity detection. This isn't just about finding exact copies; it's about spotting the subtle shifts, the rephrased sentences, or the slightly altered code snippets that try to evade detection.

You might think, "Can't I just hash the document and compare hashes?" A good start, but what if someone changes a single word or reorders a few lines of code? Your perfect hash suddenly becomes useless. At the scale of a billion documents or a hundred million lines of code submitted daily, traditional string matching or simple hashing crumbles under the computational load and fails to capture semantic similarity. This is where we need a trick, a clever mathematical shortcut that big tech relies on to find "near duplicates" efficiently.

The Scaling Challenge: Beyond Exact Matches

Imagine a system like GitHub, processing millions of new code commits every day. How do they detect if a significant portion of a new repository is copied from an existing one, perhaps with minor modifications like variable renames or comment additions? Or consider a news aggregator trying to group identical stories from different sources that have slightly rephrased headlines.

The core challenge is two-fold:

  1. Scale: Comparing every new document against every existing document is an O(N^2) operation, which quickly becomes impossible as N grows.

  2. Fuzziness: We're not looking for exact matches, but near matches. Minor alterations should still trigger a high similarity score.

This is where the elegant power of MinHash combined with Locality Sensitive Hashing (LSH) comes into play. These aren't just academic curiosities; they are foundational building blocks in systems that handle massive data volumes where approximate similarity is key.

Core Concept: MinHash – Compressing Documents into "Fingerprints"

MinHash is a technique that allows us to estimate the Jaccard similarity between two sets very efficiently, even if those sets are enormous. The magic lies in compressing a large set into a small, fixed-size "signature" or "fingerprint."

Here's the intuition:

1. Shingling: Breaking Down the Document

First, we don't treat a document as a single blob. Instead, we break it down into smaller, overlapping pieces called k-grams or "shingles." A k-gram is a sequence of k consecutive words (or characters, or tokens).

  • Example: Document "The quick brown fox" with k=2 word shingles:

  • {"The quick", "quick brown", "brown fox"}

Each document is now represented as a set of these shingles.

2. Hashing Shingles: Giving Them Identity

Next, we convert each shingle into a numerical hash value. This gives each unique shingle a compact, unique identifier. So, our document becomes a set of hash values.

3. The MinHash Signature: The Clever Compression

Now, for the genius part. Imagine you have a large set of these shingle hash values. If you apply a random permutation to all possible hash values and then pick the minimum hash value present in your document's set after that permutation, that's one "minhash."

If you do this many times with different random permutations (say, 100 to 500 times), you'll get a vector of minimum hash values. This vector is the MinHash signature for your document.

The incredible insight: The probability that the MinHash values for two documents are identical for a random permutation is equal to the Jaccard similarity of their underlying shingle sets. By comparing their signatures (the proportion of matching minhash values), we get an estimate of their true Jaccard similarity.

  • Jaccard Similarity: |A ∩ B| / |A ∪ B| (size of intersection divided by size of union).

Keep going with the full lesson

The rest of this lesson — plus its implementation guide, runnable scripts and source code — is included with the course or an All Access plan. Create a free account to start the free lessons in every course.

Already a member? Sign in