Similar Pages Should Share a Lottery Ticket

The naive near-duplicate detector has a pleasingly doomed shape:

compare every document to every other document

For a thousand documents, that is about half a million pairs. For a million documents, it is about half a trillion. The algorithm is not wrong because the similarity function is bad. It is wrong because the pair list becomes the product.

So the real problem is not:

how do we compare two documents?

It is:

how do we arrange for similar documents to find each other?

MinHash is one of those ideas that feels like a magic trick until you write the one-line proof. It turns a set similarity into a collision probability. Two documents do not need to be compared in full. They each carry a small signature. The fraction of matching signature rows estimates how much their shingle sets overlap.

Then locality-sensitive hashing adds the systems move:

do not estimate every pair
only create pairs that collide in at least one signature band

The result is not a classifier. It is a candidate generator with a dial.

First Decide What Counts as Same

Broder’s document resemblance framework starts by turning a document into a set of shingles.¹ A word shingle of width 5 is a consecutive 5-word phrase. A document becomes a set like:

{ "the model cached the prompt",
  "model cached the prompt tokens",
  "cached the prompt tokens before",
  ... }

The resemblance of two documents is the Jaccard similarity of their shingle sets:

\[J(A,B) = \frac{|A \cap B|}{|A \cup B|}.\]

This is syntactic resemblance. It is not semantic equivalence. Two documents can mean the same thing with different words and have low Jaccard. Two templated web pages can have unrelated core content and still share many boilerplate shingles. The measure is useful because many real duplicate problems are not semantic paradoxes. They are copies, mirrors, templates, syndicated text, quoted blocks, printer-friendly pages, small edits, and crawl artifacts.

That makes Jaccard a good first contract:

same local pieces, same document family

The Minimum Shingle Trick

Imagine applying a random permutation \(\pi\) to the universe of shingles. For a set \(A\), keep only the shingle whose permuted value is smallest:

\[h_\pi(A) = \arg\min_{x \in A} \pi(x).\]

Now compare two sets. The minimum element of \(A \cup B\) must lie either in the intersection or in one of the two one-sided differences. The two MinHash values match exactly when that minimum belongs to \(A \cap B\).

Since a random permutation gives every element of \(A \cup B\) the same chance to be the minimum,

\[\Pr[h_\pi(A) = h_\pi(B)] = \frac{|A \cap B|}{|A \cup B|} = J(A,B).\]

That is the trick. Similarity became a Bernoulli probability.

Repeat this with \(k\) independent permutations, or practical hash functions that approximate that behavior, and estimate:

\[\hat{J} = \frac{1}{k} \sum_{i=1}^k \mathbf{1}\{h_i(A)=h_i(B)\}.\]

Under the ideal independent-permutation model,

\[E[\hat{J}] = J, \qquad \mathrm{Var}(\hat{J}) = \frac{J(1-J)}{k}.\]

The signature length is a sampling budget. A 100-row signature is not “the document.” It is 100 noisy chances to observe the same event: does the sampled minimum of the union come from the intersection?

The min-wise independence literature exists because the phrase “random permutation of all shingles” hides an impossible object. Broder, Charikar, Frieze, and Mitzenmacher formalized when smaller permutation families behave enough like true random permutations for this estimator.² In production systems, this is one of the places where “just use a hash” deserves scrutiny.

A Little Duplicate Factory

The lab below generates two synthetic documents and one unrelated background document. All three share a controllable amount of boilerplate. The first two also share an editable core. The visualization computes exact shingle Jaccard, builds MinHash signatures, then applies LSH banding.

The important sliders are:

Text drift: edit the core document and watch exact Jaccard fall;
Boilerplate: add shared template text and watch background similarity rise;
Bands and Rows per band: reshape the candidate probability curve.

The audit badge is the same deterministic 79-check suite exported by the script. It verifies the shingle-set ledger, exact Jaccard accounting, signature agreement, all-row band collisions, LSH probability formula, threshold formula, candidate flags, pair-count arithmetic, and a few synthetic smoke cases: identical documents, dissimilar documents, and boilerplate pollution.

Text drift: 16% Boilerplate: 15% Shingle words: 4 Bands: 20 Rows per band: 5 Corpus documents: 2,000

Shared shingles or matching rows A-only shingles B-only shingles Current near pair Boilerplate background

Deterministic synthetic experiment. The MinHash rows use compact 32-bit hash functions for browser speed. The LSH curve uses the standard independent-row approximation: a pair with similarity s becomes a candidate with probability 1 - (1 - s^r)^b for b bands of r rows. The audit badge checks implementation contracts; it does not certify that a 32-bit toy hash family is suitable for adversarial web-scale indexing.

The static-site audit runner checks the exported lab contract and the default screening shape:

node - <<'NODE'
const lab = require("./assets/js/minhash-lab.js");
const EXPECTED_AUDIT = { checked: 79, failures: [], ok: true, passed: 79 };
const EXPECTED_DEFAULT = "100:20:5:126:181:0.696133:0.730000:1:0.971846:0.030508:0:0.549280:3:0";

function fixed6(value) {
  return Number(value).toFixed(6);
}

function sameJson(actual, expected) {
  return JSON.stringify(actual) === JSON.stringify(expected);
}

const audit = lab.runAudit();
const result = lab.simulate({
  bands: 20,
  boilerplate: 15,
  corpus: 2000,
  editRate: 16,
  rowsPerBand: 5,
  shingleSize: 4
});
const defaultShape = [
  result.rows,
  result.bands,
  result.rowsPerBand,
  result.exact.shared,
  result.exact.union,
  fixed6(result.exact.jaccard),
  fixed6(result.estimate),
  result.candidate ? 1 : 0,
  fixed6(result.candidateProbability),
  fixed6(result.background.jaccard),
  result.backgroundCandidate ? 1 : 0,
  fixed6(result.threshold),
  result.matches.filter(Boolean).length,
  result.backgroundMatches.filter(Boolean).length
].join(":");

if (!sameJson(audit, EXPECTED_AUDIT) || defaultShape !== EXPECTED_DEFAULT) {
  throw new Error(JSON.stringify({ audit, defaultShape }, null, 2));
}

console.log(`${audit.passed}/${audit.checked} MinHash checks passed`);
NODE

The default setting has 20 bands and 5 rows per band, so the signature has 100 rows. The red point on the S-curve is the current near pair. The gray point is an unrelated document pair that shares only the boilerplate template.

Raise text drift. Exact Jaccard falls because fewer shingles survive the edits. The MinHash estimate moves with it, but not perfectly. That noise is the point: the signature is a sample, not a proof. More rows would reduce variance, but also increase memory and hash work.

Raise boilerplate. The near pair may still be easy to catch, but the gray background point starts moving right. This is a classic failure mode. A site template, legal footer, navigation shell, or repeated product description can turn unrelated pages into weakly similar pages. MinHash did not misunderstand the data. The shingling pipeline asked it to count the wrong overlap.

Now change the banding. If a signature has \(b\) bands of \(r\) rows, and each row matches with probability \(s\), then one band matches with probability \(s^r\). The pair becomes a candidate if at least one band matches:

\[\Pr(\mathrm{candidate}\mid s) = 1 - (1-s^r)^b.\]

Increasing rows per band makes a single band stricter. Increasing bands gives the pair more chances to collide. Together they form an S-shaped screening curve. The rough threshold is:

\[s^\star \approx \left(\frac{1}{b}\right)^{1/r}.\]

This is a dangerous number if read too literally. It is not the probability that two documents are duplicates. It is only the probability that the LSH stage will send this pair to the next stage.

A Candidate Is Not a Verdict

Broder’s later near-duplicate filtering work emphasized a practical distinction: for web indexing, it is often enough to know whether resemblance is above a threshold, rather than to estimate every resemblance value.³ That is the mental model I want for LSH.

The output of LSH should be:

please compare these pairs carefully

not:

these pairs are definitely duplicates

The exact verification step can be another Jaccard computation, a containment test, a normalized edit distance on selected spans, a domain-specific rule, or a human review queue. The MinHash and LSH stages earn their keep by making that verification set small enough to afford.

This is also why false positives and false negatives have different meanings than they did in the Bloom filter post. A Bloom filter says “maybe” for membership. LSH says “maybe worth comparing” for similarity. A false positive is extra work. A false negative is a missed near-duplicate. The right operating point depends on which one hurts more.

Indyk and Motwani’s locality-sensitive hashing framework gives the general principle: construct hash functions whose collision probability is higher for near objects than far objects, then use that gap to avoid scanning everything. Their nearest-neighbor paper treats LSH as the key ingredient for sublinear search in high-dimensional settings.⁴ MinHash is the Jaccard version of that idea.

Copies Can Be Asymmetric

Jaccard is symmetric:

\[J(A,B) = \frac{|A \cap B|}{|A \cup B|}.\]

But near-duplicate systems often need an asymmetric question:

is the short document mostly contained in the long one?

A syndicated paragraph inside a long article may have low Jaccard because the union is dominated by the long article. Its containment can still be high:

\[C(A,B) = \frac{|A \cap B|}{|A|}.\]

Broder’s resemblance and containment paper treats both measures because web documents create both problems: copies with small edits, and shorter documents embedded inside longer ones.¹ A MinHash resemblance pipeline will miss some containment cases unless the system also samples or indexes for containment, uses passage-level chunks, or verifies candidate spans.

This is the same lesson wearing a different coat:

the sketch answers the question you encoded, not the question you meant

Places the Sketch Can Lie

Shingle size is a bias knob. Small shingles give high recall for edited text but also collide on common phrases. Large shingles are more discriminative but break under insertions, deletions, and reordering. There is no universally correct width. There is only a width matched to the copy process you expect.

Tokenization is part of the model. HTML stripping, Unicode normalization, stemming, punctuation, boilerplate removal, code block handling, and language segmentation all change the set. If the preprocessing changes, the signature meaning changes.

Hash collisions are not the same as textual overlap. A finite hash maps many possible shingles into fewer identifiers. At modest scale this can be harmless. At web scale, or under adversarial inputs, it becomes another source of resemblance inflation.

Banding hides variance under a threshold-shaped curve. Two pairs with the same true Jaccard can land on different sides of the candidate gate because their signatures are samples. This is why offline replay matters: evaluate recall and candidate volume on real traffic, not only on the curve.

Embeddings solve a different problem. If the task is semantic similarity, paraphrase detection, or intent clustering, MinHash over word shingles can be too literal. If the task is copy detection, crawl deduplication, template pollution, or quote overlap, that literalness is a feature.

Near-Dupe Run Sheet

Before I trust a MinHash pipeline, I want to know:

what text was removed before shingling;
whether the unit is a whole document, section, paragraph, or passage;
which shingle width was chosen and what edit process it assumes;
how many signature rows are stored per item;
which hash family and seed version define compatibility;
which banding parameters determine candidate recall;
how candidate pairs are verified after LSH;
how boilerplate-heavy domains are handled;
whether containment matters in addition to resemblance;
how recall is measured against labeled or replayed near duplicates.

The pleasant mathematical identity does not eliminate these questions. It makes them explicit.

The Lottery Ticket Picture

MinHash is not a tiny summary of what a document says.

It is a tiny summary of where the document lands under many randomized orders of its shingles. If two documents share many shingles, they often choose the same minimum. If they share few, they rarely do. Similarity becomes a collision frequency.

That is a strangely elegant bargain. Instead of asking every pair to meet, each document carries a small set of lottery tickets. Similar documents tend to hold some of the same tickets. LSH banding tells the system which shared tickets are interesting enough to inspect.

The exact pairwise comparison does not disappear. It moves to the end, where it belongs, after the sketch has made the candidate set small enough for truth to be affordable.

Primary Sources

Andrei Z. Broder, “On the Resemblance and Containment of Documents”, Compression and Complexity of Sequences, 1997. ↩ ↩²
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher, “Min-Wise Independent Permutations”, Journal of Computer and System Sciences, 2000. The conference version appeared at STOC 1998. ↩
Andrei Z. Broder, “Identifying and Filtering Near-Duplicate Documents”, Combinatorial Pattern Matching, 2000. ↩
Piotr Indyk and Rajeev Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality”, STOC, 1998. ↩