MinHash › Summary

MinHash compresses each document into a compact signature that preserves Jaccard similarity: the probability that two signatures agree at any position equals the true Jaccard similarity of the underlying shingle sets. This probabilistic identity allows you to estimate document similarity without comparing the full texts, reducing per-pair comparison cost from the document size to the signature size.

Key takeaways from this chapter:

• Jaccard similarity measures set overlap as the ratio of intersection to union, ranging from 0 to 1. It is a natural similarity measure for shingled documents and is robust to length differences between documents.
• Shingling converts documents into sets of overlapping substrings. Character-level 5-grams are the standard choice for LLM training data deduplication because they are robust to minor paraphrasing and synonym substitution.
• The MinHash identity states that for a random permutation $\pi$, the probability that the minimum elements of two sets agree is exactly the Jaccard similarity: $P(\min_\pi(A) = \min_\pi(B)) = J(A, B)$.
• MinHash signatures of length $k$ are computed by applying $k$ independent hash functions and taking the minimum hash value per function. The fraction of matching positions estimates Jaccard similarity with standard deviation $\sqrt{J(1-J)/k}$.
• LSH banding divides the signature into $b$ bands of $r$ rows, bucketing documents by their band values. Documents sharing any bucket become candidate pairs with probability $1 - (1 - s^r)^b$, creating a tunable S-curve threshold at approximately $t \approx (1/b)^{1/r}$.
• Practical tradeoffs include shingle size (character vs. word level), number of hash functions ($k$), and LSH threshold ($b$, $r$). These parameters balance precision, recall, and computational cost for the specific deduplication task.
• At LLM training scale, MinHash LSH is applied to billions of documents in distributed pipelines, reducing near-duplicate content that would otherwise distort the learned distribution, inflate benchmark scores, and increase memorization of training text.

The next chapter explores quality filtering techniques that complement deduplication by removing documents that are syntactically valid but semantically poor, completing the picture of how raw web crawl data is transformed into a high-quality training corpus.