Finding duplicate documents is easy until the collection becomes large. With one million documents, an all-pairs comparison needs roughly 500 billion checks. The important idea is therefore not a faster comparison. It is avoiding almost all comparisons.
Step 1: preserve local order with shingles
A k-shingle is a sequence of k tokens. The string abcab has the 2-shingle set {ab, bc, ca}. Unlike a bag of words, shingles retain some local order. Represent each document as a set and compare two sets with Jaccard similarity:
J(A, B) = |A intersection B| / |A union B|Small k creates accidental matches; very large k misses lightly edited copies. The right value depends on document length and the kind of edits that matter.
Step 2: replace a large set with a signature
For a random permutation of the universe, MinHash records the first member belonging to a set. The key property is:
P[minhash(A) = minhash(B)] = J(A, B)Repeat this with many hash functions. The fraction of matching signature rows estimates Jaccard similarity. More rows reduce variance but consume more memory and computation.
Step 3: use LSH as a candidate generator
Even short signatures still produce quadratic work if every pair is compared. LSH divides a signature into bands and hashes each band. Two documents become candidates when at least one band matches. More rows per band make matching stricter; more bands improve recall but admit more false positives.
In plain terms: MinHash makes each document small. LSH decides which small representations are worth checking. An exact comparison can verify the final candidates.
This is a reusable system pattern: cheap approximation first, expensive truth check second. Measure candidate reduction, recall on known duplicate pairs, and false-positive cost together; optimizing only one can make the pipeline useless.
Review card
- Shingling converts sequence similarity into set similarity.
- Jaccard compares shared elements with the union.
- MinHash preserves Jaccard similarity in expectation.
- LSH reduces search, not final verification.
- Banding trades recall against candidate volume.