Say you are building a news aggregator (like Google News). One of the biggest problems you’ll face is de-duplicating articles across millions of documents. Naive O(n^2) comparisons will crush you at scale.
MinHash + LSH is how you actually solve it.
MinHash converts a large set into a small, fixed-size signature, such that the similarity between two signatures approximates the Jaccard similarity of the original sets. Jaccard similarity is simply set intersection divided by set union; a measure of how much two sets overlap.
It is a fast, probabilistic way to estimate “how alike are these two documents?” without comparing them word by word.
The first step is shingling, where you break each document into overlapping n-grams (say, 3-word sequences), and then run MinHash on that shingle set. MinHash gives you a compact signature, typically 100-200 hash values.
The key property is that the probability that two signatures share the same minimum hash value equals the Jaccard similarity of their original shingle sets. This way, you estimate similarity without ever comparing raw text.
But you still have the comparison problem. Even with compact signatures, comparing every pair is expensive. That’s where LSH (Locality Sensitive Hashing) comes in.
You split each signature into b bands of r rows each, and hash each band into a bucket. Two documents that are similar enough will likely land in the same bucket for at least one band, and only those candidate pairs get compared.
This approach collapses billions of comparisons down to millions, and it is what systems like Google News and early web crawlers used to deduplicate content at scale. Several Google papers and engineering blogs from the early 2000s reference this exact approach. Pretty simple and neat.
As is almost always true at scale, you do not need a perfect similarity detection system. A fast, good-enough one is preferred, given that the cost is ultimately the forcing function.