Skip to content
On the Resemblance and Containment of Documents 4 min

Andrei Z. Broder · Compression and Complexity of Sequences 1997

On the Resemblance and Containment of Documents

Broder's 1997 paper behind MinHash: turn documents into sets of word groups and compare tiny sketches. Try it on your own texts.

Read the original paper

Algorithms · Yellow Belt · Pro · 4 min read

On the Resemblance and Containment of Documents

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.

Each colored bar covers two neighboring words, and each bar becomes one shingle. A document with n words gives about n minus 1 shingles. Documents that share long passages share many 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".

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 2 more diagrams and 2 interactive elements to play with

  • Compare without keeping the documents
  • A test at web scale

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.