MinHash › MinHash LSH: Finding Near-Duplicates at Scale

Computing MinHash signatures reduces the comparison problem: instead of comparing full documents (potentially thousands of characters), you compare compact $k$-dimensional integer vectors. But you still face the $O(n^2)$ pair comparison problem. For a billion documents with 128-dimensional signatures, comparing all pairs would require roughly $6.4 \times 10^{16}$ integer comparisons. Even at 10 billion comparisons per second, this would take over 6 million seconds, or about 74 days, on a single machine.

Locality Sensitive Hashing solves this by converting the problem into a bucketing problem. Instead of comparing all pairs, you organize documents into buckets such that similar documents tend to fall into the same bucket. You then only compare documents within the same bucket, dramatically reducing the number of comparisons without losing many true near-duplicate pairs.

Locality Sensitive Hashing is a general framework for approximate nearest neighbor search. The key requirement is a hash function family that is "locally sensitive," meaning pairs with high similarity hash to the same bucket with high probability, while pairs with low similarity hash to different buckets with high probability.

For MinHash, the natural LSH family is to use each component of the signature as a hash function. If two documents have the same value at position $i$ of their signatures, they hash to the same bucket under hash function $i$. By our earlier analysis, two documents share a signature value at position $i$ with probability equal to their Jaccard similarity.

A single hash function gives very coarse bucketing. With large enough buckets, everything ends up in the same bucket; with small enough buckets, nothing shares a bucket. The banding technique refines this into a more useful filter.

The standard MinHash LSH approach divides the $k$-length signature into $b$ bands of $r$ rows each, so $k = b \times r$. For each band, you hash the $r$ values in that band (treated as a unit, for example, a tuple of $r$ integers) into a bucket. Two documents become candidate pairs if and only if they share a bucket in at least one band.

The probability that two documents with true Jaccard similarity $s$ share all $r$ values in a given band is $s^r$. The probability that they do not share all values in that band is $1 - s^r$. The probability that they fail to match in all $b$ bands is $(1 - s^r)^b$. Therefore, the probability that they share at least one band (and thus become candidates) is:

$$P(\text{candidate} \mid J = s) = 1 - (1 - s^r)^b$$

where:

• $s$: the true Jaccard similarity between the pair
• $r$: the number of rows per band
• $b$: the number of bands

This function is an S-curve in $s$: it transitions sharply from near 0 (low-similarity pairs are almost never candidates) to near 1 (high-similarity pairs are almost always candidates). The location of the transition is controlled by $r$ and $b$.

The midpoint of the S-curve transition (where the probability equals 0.5) provides a useful threshold approximation. Setting $1 - (1 - t^r)^b = 0.5$ and solving approximately:

$$t \approx \left(\frac{1}{b}\right)^{1/r}$$

For example, with $b = 20$ bands and $r = 5$ rows (a 100-dimensional signature), the threshold is approximately $(1/20)^{1/5} \approx 0.55$. Pairs with Jaccard similarity well above 0.55 are detected as candidates with very high probability; pairs well below 0.55 almost never become candidates.

The S-curve sharpness increases as $r$ increases. With large $r$, the condition that all $r$ rows match is stringent, producing a sharp transition. With small $r$, the transition is more gradual because matching 2 out of 2 rows is less discriminating than matching 5 out of 5.

This tunability is one of MinHash LSH's great practical advantages. By choosing $b$ and $r$, you can set the detection threshold precisely:

• For aggressive deduplication at similarity 0.7, use $b$ and $r$ such that the S-curve midpoint falls near 0.7.
• For conservative deduplication targeting only near-perfect duplicates at similarity 0.9, use parameters that push the threshold higher.
• For a fixed budget of $k$ hash functions, you trade off sharpness versus threshold by varying how you split $k$ into $b \times r$.

LSH does not give you the exact similarity of candidate pairs. It identifies a manageable set of candidate pairs that you then verify by computing exact (or more accurate estimated) Jaccard similarity from the full signatures or from the actual shingle sets. This two-stage architecture, coarse LSH filtering followed by fine verification, makes near-duplicate detection tractable at scale.

The first stage runs in linear time per document (computing the signature and performing $b$ band hash lookups) plus time proportional to the number of candidate pairs (checking each bucket). The second stage runs in time proportional to the number of candidate pairs, which is much smaller than $n^2$ for realistic similarity distributions.

In production deduplication pipelines for LLM training, the two-stage approach looks like this. All documents are processed in parallel to compute MinHash signatures. Band hashing is performed in a distributed shuffle that groups documents by band bucket. Each bucket is then checked: if it contains more than one document, those documents are emitted as candidate pairs. The candidate pairs are then verified and deduplicated, keeping one representative from each near-duplicate cluster.

The banding technique introduces two types of errors. False positives occur when two documents that are not near-duplicates happen to share a band bucket, leading you to compare them unnecessarily. False negatives occur when two true near-duplicates fail to share any band bucket, causing them to be missed.

The S-curve shape directly characterizes these errors. At similarity $s$, the probability of a false negative is $(1 - s^r)^b$: the pair falls below the detection curve. For $s$ well above the threshold, this probability is very small. At similarity $s$, the probability of a false positive (unnecessary comparison) is the same formula applied at the wrong point: $1 - (1 - s^r)^b$ for pairs that should not be candidates. For $s$ well below the threshold, this is also very small.

Near the threshold, both errors occur with non-trivial probability. This is an inherent statistical tradeoff: no threshold-based filter can simultaneously have zero false positives and zero false negatives unless the similarity distribution has a hard gap around the threshold.

For LLM training data deduplication, some false negatives are acceptable. The goal is not perfect deduplication but substantial reduction in near-duplicate content. Missing a few near-duplicate pairs is less costly than the enormous computational burden of verifying all pairs.