MinHash

A randomized technique for estimating the Jaccard similarityJaccard similarity, n.: A simple score for how much two collections overlap: the number of items they share divided by the number of distinct items in either. Identical sets score 1; sets with nothing in common score 0. between sets — typically the sets of word or character n-grams ('shingles') in two documents — without comparing them element by element. A hash function is applied to every member of a set and only the minimum value is kept; for a random hash function, the probability that two sets share the same minimum equals their Jaccard similarity. Repeating this with k independent hash functions yields a compact signature of k numbers, and the fraction of positions where two signatures agree estimates their similarity, with error shrinking roughly as 1/√k. Combined with locality-sensitive hashinglocality-sensitive hashing, n.: A trick for finding look-alikes in a huge collection without comparing every pair: items get short codes designed so that similar items tend to share a code, and only items sharing one are compared., which buckets signatures in bands so that only likely matches are compared, MinHash finds near-duplicates among billions of documents in near-linear time. It is the workhorse of near-deduplicationdeduplication, n.: Removing repeated copies of the same or nearly the same content from a dataset, so a model does not over-learn whatever happens to be copied many times online. in language-model corpora such as FineWebFineWeb, prop. n.: A huge, free collection of cleaned-up English web text — around 15 trillion word fragments — released by Hugging Face in 2024 with a detailed public account of how it was built..

We used 5-gram shingles and 112 MinHash functions arranged in 14 bands of 8.