How do you find near-duplicate documents cheaply?

Use MinHash with 128 permutations over 5-word shingles, then LSH banding at b=42, r=3 — it found 99.47% of the near-duplicate pairs among 100,000 documents in 1.09 seconds with zero false positives, on one core of a laptop. Exact hashing found 0.12% of the same duplicates. SimHash is eight bytes a document instead of 512 and lost a quarter of them.

The duplicates below are synthetic, and that has to be said before any of the numbers. I made seven controlled edits to each generated document — one word changed, one character changed, sentences reordered, whitespace reflowed, 5% of words replaced, a paragraph appended, half a document appended. Every precision and recall figure describes behaviour on those edits, not on real web duplicates, which come from content farms, CMS templates and syndication feeds rather than from me. The shapes of the curves and the costs transfer; no specific threshold does, and the last section measures how badly one travels.

Hardware: Apple M3, 16 GB, macOS 26.4.1, Node v23.5.0. No network, no model call, no dependencies. Timings are medians of five runs after a discarded warmup, single core, in process, each method in its own process so V8 cannot deoptimise a shared loop by calling it with different parameters.

The short answer

• MinHash with 128 permutations plus LSH banding at b=42, r=3 processed 100,000 documents in 1.09 seconds — 884,637 candidate pairs examined out of 4,999,950,000 possible ones — at 0.9947 recall and 1.0000 precision.
• Exact hashing catches almost nothing. SHA-256 over raw bytes found 10 of 8,400 known duplicate pairs (recall 0.0012), and all ten were cases where a random character replacement happened to substitute a character with itself. Normalising whitespace and case first lifted it to 0.0381.
• The permutation count is not the interesting knob — the threshold is. At a threshold of 0.30, recall ran 0.9830 at 16 permutations and 1.0000 at 256. At 0.50 every count returned about 0.87, because exact Jaccard also returns 0.8705 there. You cannot beat the metric by estimating it better.
• SimHash is 64x smaller and clearly worse. Best F1 0.8248 against MinHash's 0.9999 on the same corpus, and not even cheaper to compute: 567 ms per 10,000 documents against 493 ms for MinHash at 128 permutations.
• Brute-force pairwise is the wall, and it arrives early. Comparing all 49,995,000 pairs of 10,000 documents took 8.3 seconds over MinHash signatures and 1 minute 44 seconds over the raw shingle sets. LSH cut the signature scan to 59 ms and gave up 0.5% of the recall.

What is a near-duplicate, in numbers?

The corpus is 3,100 documents: 300 originals with seven edited variants each, plus 700 unrelated ones. Median length 2,957 characters, median 340 distinct 5-word shingles, 8,400 labelled duplicate pairs out of 4,803,450 — a positive rate of 0.17%, roughly the needle proportion of a real ingest. Exact Jaccard says what each edit costs:

Across the 4,795,050 non-duplicate pairs the mean Jaccard was 0.0458 and the maximum 0.0950, a floor produced entirely by the boilerplate footer every document carries. So there is a clean gap between 0.095 and 0.52 here, and any threshold inside it separates duplicates perfectly. That gap is the most synthetic thing in the article.

Does hashing work?

No, and not by a small margin.

The ten pairs the raw hash found are the joke: the "change one character" edit picks its replacement at random, so about one time in 26 it substitutes a character with itself. Exact hashing found the edits that were not edits.

Normalisation is worth doing anyway — it is nearly free and it is the same pass the shingler needs — but it takes recall from 0.1% to 3.8%. One changed word still defeats it completely: a hash tests for identity, and near-duplicates are by definition not identical.

How many MinHash permutations do you need?

Fewer than you would guess, and the count matters far less than the threshold. Precision and recall against the 8,400 labelled pairs:

Read down the 0.50 column. Every row sits near 0.87 — including the exact Jaccard row. That is not MinHash losing anything. It is a threshold of 0.50 excluding the reordered and heavily edited variants, which genuinely have Jaccard below 0.50. Sixteen permutations already track exact Jaccard to within 0.017 at a threshold of 0.30, and 0.054 at its worst. Extra permutations buy precision at loose thresholds, not the ability to find duplicates the metric does not consider duplicates.

One measurement went the wrong way. Mean absolute error at 32 permutations came out worse than at 16 (0.0557 against 0.0519), contradicting the standard error sqrt(J(1-J)/P). Tested directly — one pair of known Jaccard, 4,000 trials with seeds redrawn each time — the estimator is unbiased and matches theory: at P=128 and J=0.60, bias −0.0004 and RMSE 0.0435 against a predicted 0.0433. It was one unlucky seed set. Re-running the corpus with 10 seed sets:

Estimation error nearly triples between the luckiest and unluckiest seed set at every count, while recall barely moves. A deployment picks one seed set and keeps it forever; at 16 or 32 permutations that choice is worth about a point of recall, and above 64 it stops mattering.

Is SimHash better?

It is 64x smaller — eight bytes against 512 — and loses a quarter of the duplicates. Sweeping the Hamming threshold for each method's best F1 on the same 3,100 documents:

Two things here surprised me. First, term-frequency weighting the SimHash changed nothing — identical results at every threshold. On 5-word shingles almost every shingle occurs exactly once, so every weight is 1 and the weighted variant is the unweighted one. TF weighting earns its keep on word-level SimHash; on shingles it is dead code.

Second, where SimHash actually fails. Per edit type, each method at its own best operating point:

SimHash handles the trivial edits and drops to about 0.75 on anything moving 35% of the shingles, paying for that recall with 629 false positives where MinHash has none. Nor can it be tuned: MinHash trades bytes for accuracy continuously through the permutation count, while SimHash's only dial is width — and doubling to 128 bits still landed below MinHash at a quarter of the permutations.

Its real advantage is comparison speed: 0.1 seconds against 8.3 for all 49,995,000 pairs of 10,000 documents. The next section takes that away.

What does fingerprinting cost?

Each method in its own process, median of five runs after a warmup:

Ten times the documents costs 10-15x the time — near enough linear, with GC making up the difference — and shingling dominates: 11.1 of the 18.6 seconds it takes to fingerprint 100,000 documents at P=128. If you are already chunking documents for retrieval, that normalisation pass is work you are doing anyway.

The surprise is SimHash: 567 ms per 10,000 documents, more than MinHash at 128 permutations. SimHash touches 64 accumulator slots per shingle; MinHash does 128 comparisons, but each is a hash and a branch over a typed array, which V8 compiles far tighter. The eight-byte fingerprint is smaller to store and no cheaper to produce.

How do you avoid comparing every pair?

You do not. At 10,000 documents there are 49,995,000 pairs; at 100,000 there are 4,999,950,000. Measured at 10,000 documents, threshold 0.30:

LSH splits the 128-slot signature into b bands of r slots and buckets documents by each band; anything sharing a whole band becomes a candidate. S* = (1/b)^(1/r) is the similarity at which a pair has a 50% chance of colliding in at least one band, and the table is essentially a plot of S* against recall. Match S to your threshold and you lose half a percent of recall for a 141x speedup.*

Both ends are traps. b=4, r=32 is 4x faster and finds 17% of the duplicates. b=64, r=2 sets S* below the 0.0950 non-duplicate ceiling, dragging in 14 million candidate pairs — 42% of all of them. LSH helps only while the candidate set stays small.

At 100,000 documents with b=42, r=3: build 755 ms, verification 333 ms, 884,637 candidates examined, 278,508 pairs flagged, recall 0.9947, precision 1.0000, 786 MB resident. Ten times the documents, a hundred times the pairs, and eighteen times the wall clock — the work is proportional to documents and candidates, not to pairs.

Where does this break?

Every precision figure above is 1.0000, which should make you suspicious. It is the one result that will not survive contact with your corpus: my unrelated documents share only a boilerplate footer, so their Jaccard tops out at 0.095 while duplicates start at 0.52. Real corpora are full of shared navigation, licence text and disclaimers. Rebuilding with a block of identical text taking a controlled share of every document, MinHash P=128:

At 30% boilerplate a threshold of 0.30 already returns more junk than duplicates; at 45% it returns roughly 114 false positives per true one. Nothing about the algorithm changed — the threshold simply fell below the p99 of the non-duplicate distribution. The transferable procedure is therefore: sample a few thousand documents you know are unrelated, measure their Jaccard distribution, and set the threshold above its 99th percentile. Ten minutes of work, and the one number here you must take from your own data rather than mine. Stripping repeated boilerplate before shingling pushes the usable threshold back down.

What should you actually use?

Under about 5,000 documents, brute-force exact Jaccard over shingle sets: it is the accuracy ceiling and it costs seconds. Do not fingerprint anything.

From 5,000 to a few million, MinHash at 128 permutations, 5-word shingles, LSH at b=42, r=3, threshold matched to your measured non-duplicate p99. That is 512 bytes a document — 51 MB for 100,000, small enough to sit beside the documents in the same SQLite file as in full-text search that works on a plane. P=64 halves the store and cost 0.0023 of recall at threshold 0.30; re-derive b and r from S* if you change P, since the banding sweep above was measured at P=128.

Use SimHash only when eight bytes a document is a hard constraint and three quarters of the duplicates is enough. Use exact hashing only as a free pre-filter in front of the real one.

And run it before you embed. Every duplicate that reaches the embedding step costs an API call and then permanently degrades retrieval by occupying a slot in every result set its original would have won — the same argument do you actually need a vector database makes from the other direction: the cheapest way to make a scan faster is to have fewer things to scan.

Check it yourself

No network, no API key, no dependencies. Save as dedupdemo.mjs and run node dedupdemo.mjs; it takes about eight seconds. It builds 2,500 documents containing 7,000 known duplicate pairs, then runs exact hashing, brute-force Jaccard, MinHash, SimHash and three LSH configurations over that corpus.

// dedupdemo.mjs -- near-duplicate detection: exact hashing vs MinHash vs
// SimHash vs LSH banding, on a corpus with KNOWN duplicate pairs.
// node dedupdemo.mjs   (no network, no deps, ~8 s)
// SYNTHETIC duplicates: the edits are ours, so recall describes these edits.
import crypto from 'node:crypto';
import fs from 'node:fs';

const BASES = 250, SINGLES = 500, K = 5, P = 128, THR = 0.30;

let s = 20260831 >>> 0;
const rnd = () => { s |= 0; s = (s + 0x6d2b79f5) | 0; let t = Math.imul(s ^ (s >>> 15), 1 | s); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
const pick = (a) => a[Math.floor(rnd() * a.length)];

// ---- vocabulary (falls back to a generated one if there is no word list) ----
let vocab;
try {
  vocab = fs.readFileSync('/usr/share/dict/words', 'utf8').split('\n').filter((w) => /^[a-z]{3,10}$/.test(w));
} catch { vocab = []; }
while (vocab.length < 20000) vocab.push('w' + vocab.length);
vocab = vocab.slice(0, 20000);
const common = vocab.slice(0, 800), topicPool = vocab.slice(800);
const BOILER = 'This document is provided by the operations team for internal reference only. Distribution outside the organisation requires written approval from the document owner.';

const sentence = (topic) => { const w = []; const n = 8 + Math.floor(rnd() * 12); for (let i = 0; i < n; i++) w.push(rnd() < 0.45 ? pick(topic) : pick(common)); return w.join(' ') + '.'; };
const para = (topic) => { const o = []; const n = 4 + Math.floor(rnd() * 4); for (let i = 0; i < n; i++) o.push(sentence(topic)); return o.join(' '); };
function makeDoc() {
  const topic = []; const tn = 40 + Math.floor(rnd() * 30);
  for (let i = 0; i < tn; i++) topic.push(pick(topicPool));
  const ps = []; const np = 3 + Math.floor(rnd() * 3);
  for (let i = 0; i < np; i++) ps.push(para(topic));
  ps.push(BOILER);
  return { text: ps.join('\n\n'), topic };
}

// ---- the controlled edits. THIS is what the recall numbers describe. ----
const EDITS = ['whitespace', 'typo', 'one-word', 'reorder-sentences', 'edit-5pct', 'append-10pct', 'append-50pct'];
function edit(kind, text, topic) {
  if (kind === 'whitespace') return text.replace(/ /g, (m) => (rnd() < 0.15 ? '  ' : ' ')).replace(/\n\n/g, '\n\n\n') + '\n   ';
  if (kind === 'typo') { let i; do { i = 20 + Math.floor(rnd() * (text.length - 40)); } while (!/[a-z]/.test(text[i])); return text.slice(0, i) + String.fromCharCode(97 + Math.floor(rnd() * 26)) + text.slice(i + 1); }
  if (kind === 'one-word') { const w = text.split(' '); w[5 + Math.floor(rnd() * (w.length - 10))] = pick(topicPool); return w.join(' '); }
  if (kind === 'reorder-sentences') return text.split('\n\n').map((p) => { const x = p.match(/[^.]+\./g); if (!x || x.length < 2) return p; for (let i = x.length - 1; i > 0; i--) { const j = Math.floor(rnd() * (i + 1)); [x[i], x[j]] = [x[j], x[i]]; } return x.map((y) => y.trim()).join(' '); }).join('\n\n');
  if (kind === 'edit-5pct') { const w = text.split(' '); const n = Math.max(1, Math.round(w.length * 0.05)); for (let i = 0; i < n; i++) w[Math.floor(rnd() * w.length)] = pick(topicPool); return w.join(' '); }
  const frac = kind === 'append-10pct' ? 0.10 : 0.50;
  let add = ''; while (add.length < text.length * frac) add += (add ? ' ' : '') + para(topic);
  return text + '\n\n' + add;
}

const docs = [], group = [];
for (let b = 0; b < BASES; b++) { const d = makeDoc(); docs.push(d.text); group.push(b); for (const k of EDITS) { docs.push(edit(k, d.text, d.topic)); group.push(b); } }
for (let i = 0; i < SINGLES; i++) { docs.push(makeDoc().text); group.push(-1 - i); }
const n = docs.length;
const isDup = (i, j) => group[i] >= 0 && group[i] === group[j];
let pos = 0; for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (isDup(i, j)) pos++;

// ---- fingerprints ----
const fmix = (h) => { h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16; return h >>> 0; };
const norm = (t) => t.toLowerCase().replace(/[^a-z0-9 ]+/g, ' ').replace(/\s+/g, ' ').trim();
function shingles(text) {
  const w = norm(text).split(' '), set = new Set();
  for (let i = 0; i + K <= w.length; i++) {
    let str = w[i]; for (let j = 1; j < K; j++) str += ' ' + w[i + j];
    let h = 0x811c9dc5; for (let c = 0; c < str.length; c++) { h ^= str.charCodeAt(c); h = Math.imul(h, 0x01000193); }
    set.add(fmix(h));
  }
  return Uint32Array.from(set).sort();
}
const jac = (a, b) => { let i = 0, j = 0, x = 0; while (i < a.length && j < b.length) { if (a[i] === b[j]) { x++; i++; j++; } else if (a[i] < b[j]) i++; else j++; } return x / (a.length + b.length - x); };
const sh = docs.map(shingles);

const seeds = new Uint32Array(P); for (let i = 0; i < P; i++) seeds[i] = (rnd() * 4294967296) >>> 0;
const sig = new Uint32Array(n * P);
for (let i = 0; i < n; i++) { const g = new Uint32Array(P).fill(0xffffffff); for (const v of sh[i]) for (let p = 0; p < P; p++) { const h = fmix(v ^ seeds[p]); if (h < g[p]) g[p] = h; } sig.set(g, i * P); }

const SL = new Uint32Array(n), SHi = new Uint32Array(n);
for (let i = 0; i < n; i++) {
  const acc = new Int32Array(64);
  for (const v of sh[i]) { const a = fmix(v ^ 0x9e3779b9), b = fmix(v ^ 0x7f4a7c15); for (let t = 0; t < 32; t++) { acc[t] += (a >>> t) & 1 ? 1 : -1; acc[32 + t] += (b >>> t) & 1 ? 1 : -1; } }
  let lo = 0, hi = 0; for (let t = 0; t < 32; t++) { if (acc[t] > 0) lo |= 1 << t; if (acc[32 + t] > 0) hi |= 1 << t; }
  SL[i] = lo >>> 0; SHi[i] = hi >>> 0;
}
const pc = (x) => { x = x - ((x >>> 1) & 0x55555555); x = (x & 0x33333333) + ((x >>> 2) & 0x33333333); x = (x + (x >>> 4)) & 0x0f0f0f0f; return Math.imul(x, 0x01010101) >>> 24; };

const ms = (t) => Number(process.hrtime.bigint() - t) / 1e6;
const row = (name, t, tp, fp) => console.log(`${name.padEnd(30)}${t.toFixed(0).padStart(8)} ms  ${(tp / (tp + fp || 1)).toFixed(4).padStart(10)}  ${(tp / pos).toFixed(4).padStart(7)}   ${(tp + fp).toString().padStart(7)}`);

console.log(`node ${process.versions.node}   ${n} docs = ${BASES} originals x ${EDITS.length + 1} variants + ${SINGLES} unrelated`);
console.log('SYNTHETIC duplicates. Recall describes OUR edit types, not the web.\n');
console.log(`${''.padEnd(30)}    time     precision   recall   flagged`);
console.log(`(${pos} labelled duplicate pairs out of ${(n * (n - 1)) / 2})`);

// exact hashing
{
  const t = process.hrtime.bigint();
  const m = new Map(); let tp = 0, fp = 0;
  for (let i = 0; i < n; i++) { const h = crypto.createHash('sha256').update(docs[i]).digest('hex'); if (!m.has(h)) m.set(h, []); m.get(h).push(i); }
  for (const ids of m.values()) for (let a = 0; a < ids.length; a++) for (let b = a + 1; b < ids.length; b++) { if (isDup(ids[a], ids[b])) tp++; else fp++; }
  row('sha256 exact', ms(t), tp, fp);
}
{
  const t = process.hrtime.bigint();
  const m = new Map(); let tp = 0, fp = 0;
  for (let i = 0; i < n; i++) { const h = crypto.createHash('sha256').update(norm(docs[i])).digest('hex'); if (!m.has(h)) m.set(h, []); m.get(h).push(i); }
  for (const ids of m.values()) for (let a = 0; a < ids.length; a++) for (let b = a + 1; b < ids.length; b++) { if (isDup(ids[a], ids[b])) tp++; else fp++; }
  row('sha256 normalised', ms(t), tp, fp);
}
// brute-force exact Jaccard
{
  const t = process.hrtime.bigint(); let tp = 0, fp = 0;
  for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (jac(sh[i], sh[j]) >= THR) { if (isDup(i, j)) tp++; else fp++; }
  row(`brute-force Jaccard >=${THR}`, ms(t), tp, fp);
}
// brute-force MinHash
{
  const t = process.hrtime.bigint(); let tp = 0, fp = 0;
  for (let i = 0; i < n; i++) { const oi = i * P; for (let j = i + 1; j < n; j++) { const oj = j * P; let eq = 0; for (let k = 0; k < P; k++) if (sig[oi + k] === sig[oj + k]) eq++; if (eq >= THR * P) { if (isDup(i, j)) tp++; else fp++; } } }
  row(`MinHash P=${P} pairwise`, ms(t), tp, fp);
}
// brute-force SimHash
{
  const t = process.hrtime.bigint(); let tp = 0, fp = 0;
  for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (pc((SL[i] ^ SL[j]) >>> 0) + pc((SHi[i] ^ SHi[j]) >>> 0) <= 16) { if (isDup(i, j)) tp++; else fp++; }
  row('SimHash 64 pairwise (<=16)', ms(t), tp, fp);
}
// LSH banding
for (const [b, r] of [[42, 3], [32, 4], [16, 8]]) {
  const t = process.hrtime.bigint();
  const pairs = new Set();
  for (let band = 0; band < b; band++) {
    const buckets = new Map();
    for (let i = 0; i < n; i++) { const o = i * P + band * r; let h = 0x811c9dc5 ^ band; for (let k = 0; k < r; k++) h = fmix(h ^ sig[o + k]); const c = buckets.get(h); if (c === undefined) buckets.set(h, i); else if (typeof c === 'number') buckets.set(h, [c, i]); else c.push(i); }
    for (const v of buckets.values()) { if (typeof v === 'number') continue; for (let a = 0; a < v.length; a++) for (let c = a + 1; c < v.length; c++) pairs.add(v[a] * n + v[c]); }
  }
  let tp = 0, fp = 0;
  for (const key of pairs) { const i = Math.floor(key / n), j = key % n; const oi = i * P, oj = j * P; let eq = 0; for (let k = 0; k < P; k++) if (sig[oi + k] === sig[oj + k]) eq++; if (eq >= THR * P) { if (isDup(i, j)) tp++; else fp++; } }
  row(`LSH b=${b} r=${r} S*=${Math.pow(1 / b, 1 / r).toFixed(2)}`, ms(t), tp, fp);
}
console.log('\nThe brute-force Jaccard row is the ceiling: no fingerprint beats it.');
console.log('If MinHash is far below it, raise P. If both are low, lower the threshold.');

On the M3 laptop above that prints:

node 23.5.0   2500 docs = 250 originals x 8 variants + 500 unrelated
SYNTHETIC duplicates. Recall describes OUR edit types, not the web.

                                  time     precision   recall   flagged
(7000 labelled duplicate pairs out of 3123750)
sha256 exact                         5 ms      1.0000   0.0010         7
sha256 normalised                   53 ms      1.0000   0.0377       264
brute-force Jaccard >=0.3         6833 ms      1.0000   1.0000      7000
MinHash P=128 pairwise             569 ms      1.0000   0.9996      6997
SimHash 64 pairwise (<=16)          11 ms      0.9381   0.7600      5671
LSH b=42 r=3 S*=0.29                18 ms      1.0000   0.9934      6954
LSH b=32 r=4 S*=0.42                24 ms      1.0000   0.9394      6576
LSH b=16 r=8 S*=0.71                 5 ms      1.0000   0.4504      3153

Change THR to 0.5 and watch every method's recall fall to about 0.87 at once. The threshold, not the fingerprint, decides what you find.