MinHash & LSH

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(n^{2})$ comparisons: with $n = 10^{8}$ that is $10^{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.

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.

<!-- {{c_layout_comment}} -->
<div id="app">
  <p class="hint">{{hint_para}}</p>
  <div id="sets-container"></div>
  <div class="controls">
    <button id="btn-run" type="button">{{btn_run}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div id="bucket-panel" class="bucket-panel hidden">
    <h3 class="bucket-title">{{bucket_title}}</h3>
    <div id="buckets"></div>
  </div>
  <div id="status" class="status"></div>
</div>

/* {{c_base_styles}} */
* { 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; }
/* {{c_set_row_styles}} */
.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; }
/* {{c_control_styles}} */
.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; }
/* {{c_bucket_styles}} */
.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; }
/* {{c_status_styles}} */
.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; }

// Code not found

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 magic is in the math. Define the Jaccard similarity of two sets $A$ and $B$ as

$$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 $k$ independent random permutations $\pi_{1}, \dots, \pi_{k}$ of the universe of tokens. The MinHash signature of a set $S$ is the vector $h(S) = (\min_{x \in S}\pi_{1}(x),\, \dots,\, \min_{x \in S}\pi_{k}(x))$. The key theorem:

$$\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 $k$ positions the variance shrinks as $1/k$.

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

$$p_{\text{candidate}} = 1 - \bigl(1 - J^{r}\bigr)^{b}$$

By tuning $b$ and $r$ you slide the S-curve: high-similarity pairs collide with high probability, low-similarity pairs almost never collide. The total work is $O(n \cdot k)$ to build signatures plus $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.

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 $n$-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 $k$-mer sets (strings of $k$ 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.

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.