MinHash › From Sets to Shingles

To apply Jaccard similarity to documents, you first convert each document into a set of overlapping substrings called shingles or k-grams. A shingle of size $k$ is a contiguous sequence of $k$ characters or $k$ words extracted by sliding a window of length $k$ across the document one step at a time.

Character-level shingles (for example, 5-character n-grams) offer fine-grained coverage of document content. The sentence "hello world" produces 5-gram character shingles: {hello, ello , llo w, lo wo, o wor, worl, world}. Notice that whitespace is included in the shingles, so word boundaries are implicitly captured.

Character-level shingles are robust to synonym substitution because replacing one word with a synonym changes many character-level shingles but preserves all the others. They are also more robust to minor formatting differences, like added punctuation or changed capitalization (after lowercasing). The main drawback is that they produce many more shingles per document than word-level shingles, increasing memory requirements during signature computation.

Word-level shingles treat words as the atomic units. A 3-word shingle captures consecutive trigrams of words, which are sensitive to phrase-level structure. Word-level shingles are better at capturing semantic phrases like "machine learning model" as a unit, making them more sensitive to reorderings and paraphrasings that preserve individual words but change their arrangement.

The downside of word-level shingles is sensitivity to synonym substitution: replacing "big" with "large" changes a word-level shingle entirely while barely changing the character-level representation. For near-duplicate detection of web documents where paraphrasing is the primary near-duplicate mechanism, character-level shingles typically perform better.

The choice of $k$ has a direct effect on sensitivity. Very short shingles (k=2 or k=3 characters) appear so frequently across unrelated documents that even dissimilar texts get high Jaccard similarity by chance. Very long shingles (k=20+ characters) become unique to each document, causing near-duplicates that differ slightly to appear unrelated.

In practice, most deduplication pipelines for LLM training use character-level shingles with $k$ between 5 and 9. The exact value is usually determined empirically by checking whether known near-duplicate pairs get high Jaccard scores and known unrelated pairs get low scores on a small labeled sample. The Pile, RefinedWeb, and similar datasets used $k = 5$ character shingles as a standard choice.

You can represent the shingle set compactly using a hash function. Rather than storing the raw strings (which can be hundreds of bytes for long shingles or many bytes even for short ones), you hash each shingle to a 32-bit or 64-bit integer. This trades a small collision probability for a large memory reduction. With 64-bit hashes, the probability of any two distinct shingles colliding is approximately $1 / 2^{64}$, which is negligible in practice.

Hashing shingles to integers also accelerates the MinHash computation, because comparing integers is faster than comparing strings, and the subsequent hash function computations operate directly on integer inputs.