Search engines and news sites face a quiet problem: the same text shows up again and again. A page is copied, a story is reposted with a new headline, or a mirror site repeats it word for word. Finding these near duplicates is hard, because the copies are rarely exactly alike.
In 1997 Andrei Broder, working on the AltaVista search engine, described a neat way to measure how alike two documents are, and to do it with a tiny summary of each. His idea, now called MinHash, is used wherever very large collections of text, pages or sets must be compared.
Cut each document into overlapping word groups called shingles. Two documents' resemblance is the share of shingles they have in common out of all the shingles they have. To avoid comparing whole documents, keep only a few of the smallest hashed shingles as a sketch. The sketches alone give a good estimate of the resemblance.
Turn a document into a set
Broder wants a measure that matches the everyday idea of "roughly the same". He first turns each document into a set of shingles. A shingle is a short run of neighboring words. The paper calls its length w. Overlapping runs mean that a small edit only spoils a few shingles.
Now two documents are two sets, and the paper defines their resemblance in the plainest way possible: the number of shingles in both sets, divided by the number of shingles in either. This is a number from 0 to 1. A document resembles itself fully. Unrelated documents score near zero.
The paper also defines containment, which asks how much of one document lies inside another. Resemblance suits "are these copies of each other", and containment suits "is this a quote from that".
