Introduction

Imagine you have a hundred million web pages and you want to find all the pairs that are nearly identical — plagiarism, mirrors, near-duplicate news articles. Comparing every pair naively costs O(n2)O(n^{2}) comparisons: with n=108n = 10^{8} that is 101610^{16} operations. Hopeless.

MinHash and Locality-Sensitive Hashing (LSH) are the two ideas that make this problem tractable.

The core insight: instead of comparing documents directly, shrink each one into a tiny sketch (a few hundred integers) such that the probability two sketches collide on a single position equals the Jaccard similarity of the original sets. Then LSH groups items into buckets — items in the same bucket are candidates worth checking, everything else is ignored.

The technique was introduced by Andrei Broder in 1997 while working on AltaVista's web-crawl deduplication. It remains one of the most elegant and practically important ideas in data engineering.

Try It

Each row below is a set of tokens (words in a document). MinHash computes a short signature for each set, then LSH assigns every set to a bucket. Sets that share a bucket are near-duplicates.

<!-- Main demo layout -->
<div id="app">
  <p class="hint">Each set is a bag of tokens (words). Click tokens to add or remove them. Then run MinHash + LSH to see which sets land in the same bucket.</p>
  <div id="sets-container"></div>
  <div class="controls">
    <button id="btn-run" type="button">Run MinHash + LSH</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div id="bucket-panel" class="bucket-panel hidden">
    <h3 class="bucket-title">LSH Buckets (shared bands)</h3>
    <div id="buckets"></div>
  </div>
  <div id="status" class="status"></div>
</div>

/* Base reset and typography */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; font-size: 14px; }
#app { padding: .6rem .4rem; }
.hint { font-size: .85rem; color: #444; margin-bottom: .8rem; line-height: 1.45; }
/* Set rows and token chips */
.set-row { display: flex; align-items: flex-start; gap: .5rem; margin-bottom: .55rem; flex-wrap: wrap; }
.set-label { font-weight: 700; min-width: 2.2rem; padding-top: .18rem; color: #1d3557; }
.tokens { display: flex; flex-wrap: wrap; gap: 4px; flex: 1; }
.token { background: #dce8f5; border: 1px solid #9bbbd4; border-radius: 5px;
         padding: 2px 7px; font-size: .82rem; cursor: pointer; user-select: none;
         transition: background .12s, border-color .12s; }
.token:hover { background: #c3d8ee; }
.token.active { background: #1d3557; color: #fff; border-color: #1d3557; }
/* Button controls */
.controls { margin: .7rem 0 .5rem; display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
/* LSH bucket display */
.bucket-panel { margin-top: .5rem; }
.bucket-title { font-size: .9rem; font-weight: 700; margin-bottom: .4rem; color: #1d3557; }
.bucket-grid { display: flex; gap: .5rem; flex-wrap: wrap; }
.bucket { border: 2px solid #adb5bd; border-radius: 8px; padding: .35rem .6rem;
          min-width: 5rem; background: #f8f9fa; }
.bucket.match { border-color: #2a9d8f; background: #e8f8f5; }
.bucket-id { font-size: .72rem; color: #666; margin-bottom: .2rem; }
.bucket-items { display: flex; flex-wrap: wrap; gap: 4px; }
.badge { border-radius: 5px; padding: 2px 8px; font-size: .8rem; font-weight: 700;
         color: #fff; }
/* Status bar */
.status { font-size: .88rem; font-weight: 600; min-height: 1.3em; margin-top: .4rem; }
.status.ok { color: #2a7d4f; }
.status.info { color: #1d3557; }
.hidden { display: none; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// MinHash + LSH demo
// Collision probability of one hash position = Jaccard(A,B). With K positions split into B bands of R rows, P(candidate) = 1-(1-J^R)^B.
const COLORS = ['#e63946','#457b9d','#2a9d8f','#e76f51','#6a4c93'];
// Fixed token universe (indices used as integers for hashing)
const UNIVERSE = ['cat','dog','fish','bird','fox','ant','bee','cow','elk','gnu',
                  'hat','cup','pen','key','box','jar','rug','map','gem','nut'];
// Preset sets: S1 and S2 share 3/7 tokens (Jaccard ~0.43); S3 is completely different
const INIT_SETS = [
  ['cat','dog','fish','bird','fox'],
  ['cat','dog','fish','ant','bee'],
  ['hat','cup','pen','key','box'],
];
// K=20 hash functions split into B=10 bands of R=2 rows each (P(candidate|J=0.43) ~ 0.87)
const K = 20;
const B = 10;
const R = K / B;
// Build K independent hash functions (linear congruential mod large prime)
function makeHashFns(k) {
  const fns = [];
  // Large prime for modular arithmetic
  const P = 1048583;
  for (let i = 0; i < k; i++) {
    const a = (i * 2654435761 + 1) >>> 0;
    const b = (i * 2246822519 + 7) >>> 0;
    fns.push(x => ((a * x + b) % P));
  }
  return fns;
}
const HASH_FNS = makeHashFns(K);
// Compute MinHash signature of length K for a set of tokens
function minhashSig(tokens) {
  const indices = tokens.map(t => UNIVERSE.indexOf(t)).filter(i => i >= 0);
  return HASH_FNS.map(h => {
    let mn = Infinity;
    for (const idx of indices) { const v = h(idx); if (v < mn) mn = v; }
    return mn;
  });
}
// Return the B band-bucket keys for a signature
function lshBuckets(sig) {
  const keys = [];
  for (let band = 0; band < B; band++) {
    const slice = sig.slice(band * R, (band + 1) * R).join(',');
    keys.push('b' + band + ':' + slice);
  }
  return keys;
}
// Exact Jaccard similarity (for status display only)
function jaccard(a, b) {
  const sa = new Set(a), sb = new Set(b);
  let inter = 0;
  for (const x of sa) if (sb.has(x)) inter++;
  return inter / (sa.size + sb.size - inter);
}
let sets = INIT_SETS.map(s => new Set(s));
function renderSets() {
  const container = document.getElementById('sets-container');
  container.innerHTML = '';
  sets.forEach((s, i) => {
    const row = document.createElement('div');
    row.className = 'set-row';
    const lbl = document.createElement('span');
    lbl.className = 'set-label';
    lbl.textContent = 'S' + (i + 1);
    lbl.style.color = COLORS[i % COLORS.length];
    row.appendChild(lbl);
    const toks = document.createElement('div');
    toks.className = 'tokens';
    UNIVERSE.forEach(tok => {
      const span = document.createElement('span');
      span.className = 'token' + (s.has(tok) ? ' active' : '');
      span.textContent = tok;
      span.title = 'Click to toggle this token';
      span.addEventListener('click', () => {
        s.has(tok) ? s.delete(tok) : s.add(tok);
        renderSets();
        hideBuckets();
      });
      toks.appendChild(span);
    });
    row.appendChild(toks);
    container.appendChild(row);
  });
}
function hideBuckets() {
  document.getElementById('bucket-panel').classList.add('hidden');
  setStatus('', '');
}
function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + cls;
}
// Run MinHash on all sets, then group into LSH buckets
function run() {
  const sigs = sets.map(s => minhashSig([...s]));
  // Map band-bucket key to list of set indices
  const bucketMap = {};
  sigs.forEach((sig, i) => {
    lshBuckets(sig).forEach(key => {
      if (!bucketMap[key]) bucketMap[key] = [];
      bucketMap[key].push(i);
    });
  });
  // Collect candidate pairs that share at least one band bucket
  const candidatePairs = new Set();
  for (const members of Object.values(bucketMap)) {
    for (let a = 0; a < members.length; a++) {
      for (let bb = a + 1; bb < members.length; bb++) {
        const key = members[a] + '-' + members[bb];
        candidatePairs.add(key);
      }
    }
  }
  // Render only buckets that contain more than one set
  const panel = document.getElementById('bucket-panel');
  const grid = document.getElementById('buckets');
  grid.innerHTML = '';
  const bucketGrid = document.createElement('div');
  bucketGrid.className = 'bucket-grid';
  for (const [key, members] of Object.entries(bucketMap)) {
    if (members.length < 2) continue;
    const bEl = document.createElement('div');
    bEl.className = 'bucket match';
    const idEl = document.createElement('div');
    idEl.className = 'bucket-id';
    idEl.textContent = 'Band ' + key.split(':')[0].toUpperCase();
    bEl.appendChild(idEl);
    const items = document.createElement('div');
    items.className = 'bucket-items';
    members.forEach(i => {
      const badge = document.createElement('span');
      badge.className = 'badge';
      badge.style.background = COLORS[i % COLORS.length];
      badge.textContent = 'S' + (i + 1);
      items.appendChild(badge);
    });
    bEl.appendChild(items);
    bucketGrid.appendChild(bEl);
  }
  if (bucketGrid.children.length === 0) {
    const none = document.createElement('span');
    none.textContent = 'No shared buckets — sets are too different.';
    none.style.color = '#888';
    bucketGrid.appendChild(none);
  }
  grid.appendChild(bucketGrid);
  panel.classList.remove('hidden');
  // Show exact Jaccard for S1 vs S2 as a reference
  let statusMsg = '';
  if (sets.length >= 2) {
    const j12 = jaccard([...sets[0]], [...sets[1]]);
    statusMsg = i18nFmt('S1 vs S2 Jaccard similarity: %j%', { j: j12.toFixed(2) });
  }
  setStatus(statusMsg, 'info');
}
document.getElementById('btn-run').addEventListener('click', run);
document.getElementById('btn-reset').addEventListener('click', () => {
  sets = INIT_SETS.map(s => new Set(s));
  renderSets();
  hideBuckets();
});
renderSets();
Result
Console

Notice: two sets with high Jaccard similarity land in the same bucket almost every time. A set that is completely different lands alone. This is not magic — it is the mathematical guarantee that the collision probability equals the Jaccard similarity.

The Real Complexity

The magic is in the math. Define the Jaccard similarity of two sets AA and BB as

J(A,B)=∣A∩B∣∣A∪B∣J(A,B) = \frac{|A \cap B|}{|A \cup B|}

This is 1 when the sets are identical and 0 when they share nothing.

MinHash picks kk independent random permutations π1,…,πk\pi_{1}, \dots, \pi_{k} of the universe of tokens. The MinHash signature of a set SS is the vector h(S)=(min⁡x∈Sπ1(x), …, min⁡x∈Sπk(x))h(S) = (\min_{x \in S}\pi_{1}(x),\, \dots,\, \min_{x \in S}\pi_{k}(x)). The key theorem:

Pr⁡[min⁡x∈Aπ(x)=min⁡x∈Bπ(x)]=J(A,B)\Pr\bigl[\min_{x \in A}\pi(x) = \min_{x \in B}\pi(x)\bigr] = J(A,B)

So each signature position is an independent unbiased estimator of the Jaccard similarity. With kk positions the variance shrinks as 1/k1/k.

LSH then splits the kk hash values into bb bands of rr rows each (so k=b⋅rk = b \cdot r). Two sets become candidates if and only if all rr rows in at least one band match exactly. The probability of becoming a candidate is

pcandidate=1−(1−Jr)bp_{\text{candidate}} = 1 - \bigl(1 - J^{r}\bigr)^{b}

By tuning bb and rr you slide the S-curve: high-similarity pairs collide with high probability, low-similarity pairs almost never collide. The total work is O(n⋅k)O(n \cdot k) to build signatures plus O(n⋅b)O(n \cdot b) to fill buckets — sub-quadratic even for billions of items.

Unlike pattern matching (exact text search) or sequence alignment (edit distance), MinHash/LSH trades an exact answer for a probabilistic one — a classic approximation algorithm bargain.

Where It Matters

MinHash and LSH are workhorses of modern data systems:

  • Web deduplication: search engines use LSH every crawl cycle to avoid indexing near-identical pages, saving storage and ranking quality. AltaVista was the first; every major engine followed.
  • Plagiarism detection: academic and legal systems fingerprint documents as shingles (overlapping word nn-grams), then MinHash/LSH finds pairs above a similarity threshold in seconds.
  • Recommendation systems: user–item interaction sets are MinHashed; similar users end up in the same LSH bucket and become candidates for collaborative filtering.
  • Genomics: comparing DNA sequences as kk-mer sets (strings of kk consecutive nucleotides) with MinHash is orders of magnitude faster than alignment for large-scale genome assembly and metagenomics.
  • Vector search (approximate nearest neighbors): random-projection LSH generalises the idea from sets to vectors, powering image search, embedding retrieval, and neural network similarity lookups at billion-point scale.

Any time you need to find "things that are close" in a huge collection, some variant of LSH is probably under the hood.

Conclusion

MinHash and LSH solve a problem that brute force can never touch at scale: finding near-duplicates in millions or billions of items without comparing every pair.

The trick is beautiful in its simplicity. A random permutation of the universe of tokens turns set similarity into a coin flip. Many such flips give a reliable sketch. LSH then uses those sketches to route similar items into the same bucket — turning a quadratic search into a near-linear one, with a tunable accuracy guarantee.

The next time a search engine serves you without duplicates, a recommender suggests someone with your taste, or a genomics pipeline assembles a genome in hours rather than years, there is a good chance that MinHash and LSH are working quietly in the background — flipping random coins that always land in the right bucket.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/locality-sensitive-hashing-minhash/Content licensed under CC BY-NC 4.0.