---
title: What is shingling? k-shingles, MinHash, and Jaccard similarity
canonical: https://telnyx.com/learn-ai/shingle-example-real-analysis
---
# What is shingling? k-shingles, MinHash, and Jaccard similarity

[Start building](https://telnyx.com/sign-up)

### Ask AI

* [![GPT](https://d2efw2akbx8gaf.cloudfront.net/https://dotcom-payload-assets-prod.s3.us-east-1.amazonaws.com/cms-media/chatgpt_icon-ea55e09d.jpeg?width=92&format=webp)](https://chat.openai.com/?q=What makes Telnyx's global network different, breakdown call quality for normal phone calls and voice AI calls.)
* [![Claude](https://d2efw2akbx8gaf.cloudfront.net/https://dotcom-payload-assets-prod.s3.us-east-1.amazonaws.com/cms-media/claude_icon-c7c8eef3.webp?width=92&format=webp)](https://claude.ai/new?q=What makes Telnyx's global network different, breakdown call quality for normal phone calls and voice AI calls.)
* [![Perplexity](https://d2efw2akbx8gaf.cloudfront.net/https://dotcom-payload-assets-prod.s3.us-east-1.amazonaws.com/cms-media/perplexity_icon-cd5b74f1.webp?width=92&format=webp)](https://www.perplexity.ai/search?q=What makes Telnyx's global network different, breakdown call quality for normal phone calls and voice AI calls.)
* [![Gemini](https://d2efw2akbx8gaf.cloudfront.net/https://dotcom-payload-assets-prod.s3.us-east-1.amazonaws.com/cms-media/gemini_icon-4ff1cbf4.webp?width=92&format=webp)](https://www.google.com/search?udm=50&aep=11&q=What makes Telnyx's global network different, breakdown call quality for normal phone calls and voice AI calls.)
* [![Grok](https://d2efw2akbx8gaf.cloudfront.net/https://dotcom-payload-assets-prod.s3.us-east-1.amazonaws.com/cms-media/grok_icon-e588e5bd.webp?width=92&format=webp)](https://x.com/i/grok?text=What makes Telnyx's global network different, breakdown call quality for normal phone calls and voice AI calls.)

[Back to Glossary](https://telnyx.com/learn-ai)

# What is shingling? k-shingles, MinHash, and Jaccard similarity

Shingling splits text into overlapping k-shingles so near-duplicate documents can be found. How Jaccard similarity, MinHash, and LSH work, with examples.

Editor: [Maeve Sentner](https://www.linkedin.com/in/maevesentner/)

**Updated October 2026**

Shingling is a way to compare documents by the short runs of text they share. It breaks a continuous sequence of text, data, or signals into overlapping chunks of length k, called shingles or k-shingles, to analyze local patterns, compute metrics, or measure similarity. Two documents that share most of their shingles are near-duplicates, even when a few words were changed, added, or moved.

Near-duplicates are still a live problem in the age of large language models. In 2022, [Lee and colleagues](https://arxiv.org/abs/2107.06499) found that over 1% of the unprompted output of language models trained on standard datasets was copied verbatim from the training data. To clean that data, they removed exact repeated passages and compared documents by their 5-word shingles with MinHash, the sampling trick described below. Models trained on the deduplicated data emitted memorized text ten times less often.

This content was generated with the assistance of AI. Our AI [prompt chain](https://telnyx.com/learn-ai/promptchain-ai) workflow is carefully [grounded](https://telnyx.com/learn-ai/grounding-ai) and preferences .gov and .edu citations when available. **All content is reviewed by a Telnyx employee to ensure accuracy, relevance, and a high standard of quality.**

## Sign up and start building.

[Sign Up](https://telnyx.com/sign-up)[Contact Us](https://telnyx.com/contact-us)

Shingling in this sense has nothing to do with roof shingles, the shingles virus, the shingling method for curly hair, or shingle theory in securities law.

## What is a shingle?

A shingle is one window of k consecutive tokens taken from a sequence, and a document's shingles are every such window, each one overlapping the next. The textbook _Mining of Massive Datasets_ by [Leskovec, Rajaraman, and Ullman](http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf) defines a k-shingle as any substring of length k found in a document. It then treats the document as the set of k-shingles that appear in it one or more times. Broder called it w-shingling, with w for the window size.

The tokens can be characters or words:

* Character 3-shingles of "abcab" are abc, bca, and cab. The window slides one character at a time.
* Word 3-shingles of "the cat sat on the mat" are "the cat sat", "cat sat on", "sat on the", and "on the mat". A six-word sentence yields four word 3-shingles, because the last full window starts at the fourth word.

Because a document becomes a set, a shingle that repeats counts once, and the order of the shingles no longer matters. That is what makes shingling tolerant of edits: moving a paragraph changes only the few shingles that cross its edges, while every shingle inside the paragraph survives.

## How does shingling measure document similarity?

Shingling measures similarity by comparing two documents' shingle sets with the Jaccard similarity. That score is the number of shingles the sets share divided by the number of distinct shingles in either set. _Mining of Massive Datasets_ writes it as |S ∩ T| / |S ∪ T|. A score of 1 means the two sets are identical, and 0 means they share nothing.

The sentences "the cat sat on the mat" and "the cat sat on a mat" differ by one word. Their word 3-shingles are:

* First sentence: the cat sat, cat sat on, sat on the, on the mat.
* Second sentence: the cat sat, cat sat on, sat on a, on a mat.

They share 2 shingles, and there are 6 distinct shingles across both, so the Jaccard similarity is 2 / 6, or about 0.33\. One changed word removed two of each sentence's four shingles, because every word sits inside up to k shingles. On a long document the same one-word edit barely moves the score. Shingling looks harsh on toy sentences and works well on real documents.

Measuring document similarity by shared shingles goes back to [Andrei Broder](https://doi.org/10.1109/SEQUEN.1997.666900) and his 1997 paper on the resemblance and containment of documents. Broder and colleagues applied the same method to [cluster the web](https://doi.org/10.1016/S0169-7552%2897%2900031-7) by syntactic similarity that year.

Broder's paper defines two scores. Resemblance is the Jaccard similarity above. Containment divides the shared shingles by the size of one document's set only, |S(A) ∩ S(B)| / |S(A)|, and equals 1 when A appears whole inside B. Containment catches the case resemblance misses: a short page quoted in full inside a much longer one shares all of its shingles with the longer page, yet its Jaccard score stays low.

## How to choose the shingle size k

The shingle size k should be large enough that any given shingle is unlikely to appear in any given document by chance. For character shingles, _Mining of Massive Datasets_ suggests k = 5 for a corpus of emails and says k = 9 is considered safe for large documents such as research articles. Word shingles need a smaller k, because each word carries more information than a character; Lee and colleagues used word 5-grams. When k is too small, unrelated documents share common shingles and look similar.

With 27 characters, letters plus a space, there are 27^5, or 14,348,907, possible 5-shingles, far more than the characters in a typical email. Real text uses common letters far more often than rare ones, which shrinks the effective alphabet. So the authors' rule of thumb counts only 20 characters. Estimate the possible k-shingles as 20^k, and keep that number far above the length of a typical document.

Larger k has a cost in the other direction. Every token belongs to up to k shingles, so a single edit removes more shingles as k grows, and two documents with scattered small changes start to look unrelated. Word shingles behave like long character shingles: a word 3-shingle spans far more characters than a character 3-shingle.

Whatever the unit, the text is normalized first; the textbook suggests replacing every run of white-space characters with a single blank, and the code below also lowercases.

Two practical refinements come from the same textbook:

* Hashing each shingle to a 4-byte number saves space. Nine-character shingles hashed to 4 bytes separate documents better than 4-character shingles stored as is, though both take 4 bytes per shingle. Most 4-byte sequences are unlikely or impossible as 4-character text, while the hashed 9-character shingles spread across almost all of them.
* Shingles built around stop words suit prose. For finding pages that carry the same news article, a shingle defined as a stop word followed by the next two words worked well. The article's prose contributes many such shingles, while an ad such as "Buy Sudzo", the textbook's example, contains no stop words and so contributes none.

## Shingling at scale: MinHash and locality-sensitive hashing

MinHash makes shingling practical at scale. It replaces each document's full set of shingles with a short signature, and the share of positions where two signatures agree estimates their Jaccard similarity. Comparing every pair of shingle sets directly costs too much on a large corpus. A shingle set can take several times the space of the document itself, and the number of pairs grows with the square of the number of documents.

A minhash function shuffles the possible shingles into a fixed random order. It then records the first shingle, in that order, that a document contains. Real systems don't shuffle billions of hashed shingles. As the textbook describes, each minhash uses a random hash function instead.

MinHash traces to Broder's random-permutation sketches. It rests on one property, as _Mining of Massive Datasets_ states it: the probability that a minhash function gives the same value for two sets equals their Jaccard similarity. So a signature made of many independent minhash values estimates the similarity: if two signatures agree in 60 of 100 positions, the documents' Jaccard similarity is about 0.6.

### Locality-sensitive hashing

Locality-sensitive hashing (LSH) avoids comparing every pair of signatures. [Indyk and Motwani](https://doi.org/10.1145/276698.276876) introduced LSH in 1998 for approximate nearest-neighbor search, and the banding version used with MinHash works like this:

1. Split each signature into b bands of r values, so b × r equals the signature length.
2. Hash each band. Documents whose band hashes collide in at least one band become a candidate pair.
3. Verify only the candidate pairs with an exact score, such as the true Jaccard similarity or, as Lee and colleagues did, edit similarity.

Two documents with Jaccard similarity s become a candidate pair with probability 1 − (1 − s^r)^b. That function forms an S-curve: pairs well above a threshold set by b and r usually collide, pairs well below it usually do not, and more bands and rows make the turn sharper. Choosing b and r trades missed duplicates against wasted comparisons.

_Mining of Massive Datasets_ defines the threshold as the similarity at which a pair has an even chance of becoming a candidate, and gives (1/b)^(1/r) as an approximation. For 16 bands of 4 rows the approximation is 0.5, while the exact probability at s = 0.5 is about 0.64\. Pairs at s = 0.3 still become candidates about 12% of the time.

### Deduplicating LLM training data

Lee and colleagues applied MinHash to language model training data. They split each document on spaces, represented it by its word 5-grams, and built MinHash signatures of 9,000 values. Their paper writes the candidate probability as 1 − (1 − s^b)^r with b = 20 and r = 450, which swaps the two letters relative to the textbook. In the textbook's notation, that is 450 bands of 20 values, with the threshold near (1/450)^(1/20), about 0.74.

A MinHash match was only a candidate. Lee and colleagues counted two documents as duplicates when they matched and their edit similarity was greater than 0.8\. Edit similarity is 1 minus the edit distance divided by the longer document's length. They linked matching documents into clusters, and when a duplicate spanned data splits they kept the copy in the test or validation set and removed it from training. Before deduplication, train-test overlap affected over 4% of the validation sets of standard datasets.

## Shingling numeric sequences and data streams

Shingling also applies to numbers: a shingle of size k turns a stream of values into a series of overlapping k-value windows, each treated as one point. [Guha and colleagues](https://proceedings.mlr.press/v48/guha16.pdf) used shingling for anomaly detection on streams in their 2016 robust random cut forest method. A shingle of size 4 treats each run of four consecutive values as a 4-dimensional point. Each shingle captures the typical shape of the curve, and a departure from that shape can signal an anomaly.

A daily price series shows the windows. With prices 100, 102, 101, 105, and 108 and k = 3, the shingles are \[100, 102, 101\], \[102, 101, 105\], and \[101, 105, 108\]. Each window can feed a statistic: their means are 101.0, about 102.67, and about 104.67, the same windows a 3-day rolling average uses.

The shingle size trades sensitivity against delay. Guha and colleagues note that shingles that are too small may catch naturally varying noise and trigger false alarms, while shingles that are too large may slow detection or miss the anomaly altogether.

## Shingling vs embeddings

Shingling finds documents that share exact text, while embeddings find documents that share meaning. A shingle set records which runs of tokens a document contains, so it catches copying, templated text, and light edits, and it misses a paraphrase that uses different words. An embedding model maps text to a vector of numbers, placed so that texts with similar meaning sit close together. It catches the paraphrase, but it scores a verbatim copy and a close rewording almost the same.

The two fit different jobs:

* Shingling with MinHash suits deduplication, plagiarism detection, and finding mirrored or templated web pages. It needs no trained model, and the score it estimates, shared shingles over all distinct shingles, is easy to explain.
* Embeddings suit [semantic search](https://telnyx.com/resources/embeddings-database), recommendations, and retrieval for a language model, where the question rarely repeats the document's words.

A pipeline can use both. A corpus is deduplicated with shingles first, so near-copies don't crowd the results, and then embedded for search. The Telnyx [Embeddings API](https://telnyx.com/products/embeddings-api) handles the second step: it converts stored documents into vector embeddings for semantic search and returns the most similar document chunks for a query.

## Example: k-shingles and Jaccard similarity in Python

Computing word shingles and their Jaccard similarity takes a few lines of Python, and the result matches the 0.33 worked out by hand above:

```
def shingles(text, k=3):
    words = text.lower().split()
    return {" ".join(words[i:i + k]) for i in range(len(words) - k + 1)}

def jaccard(a, b):
    return len(a & b) / len(a | b)

s1 = shingles("the cat sat on the mat")
s2 = shingles("the cat sat on a mat")
print(sorted(s1 & s2))            # ['cat sat on', 'the cat sat']
print(round(jaccard(s1, s2), 2))  # 0.33
```

For character shingles, slide over the string instead of the word list, with `{text[i:i + k] for i in range(len(text) - k + 1)}`. At corpus scale, replace the exact Jaccard step with MinHash signatures and LSH banding, as described above.

## Frequently asked questions

### What is the shingling method?

The shingling method splits a document into overlapping chunks of k tokens, called shingles, and compares documents by the share of shingles they have in common. In data mining it is used to find near-duplicate documents and to detect plagiarism. The phrase also names a hair-styling technique for defining curls, which is unrelated.

### What are k-shingles?

K-shingles are all the substrings of length k in a document, taken one position apart so that they overlap. The k-shingles of a document form a set, and comparing two sets with the Jaccard similarity shows how much text the documents share. For character shingles, common choices are k = 5 for short texts such as emails and k = 9 for long documents.

### Is shingling the same as n-grams?

Shingling and n-grams use the same windows: a k-shingle is an n-gram with n = k. The difference is in how they are used. Shingling treats a document as a set of its n-grams and compares sets for similarity, while n-gram language models count n-grams to predict the next word.

### Is shingling a concept in real analysis?

Shingling is not a concept in real analysis, the branch of mathematics that studies limits, continuity, and the real numbers. It is a data-mining technique for comparing sequences through overlapping windows. A sliding-window statistic, such as a rolling average over shingles of a price series, is arithmetic on those windows, not real analysis.

### What does shingle theory mean?

Shingle theory is a doctrine in US securities law, unrelated to text shingling. As an [SEC speech](https://www.sec.gov/newsroom/speeches-statements/spch398-self-regulation-new-era) summarized it in 2000, a firm that holds itself out to the public as offering to do business implicitly represents that it will do so in a fair and honest manner. It shares only the word "shingle" with the data-mining technique.

### What is shingling in data mining?

Shingling in data mining is the first step in finding similar items in large collections: each document becomes a set of shingles, and the sets are compared with the Jaccard similarity. To scale, the sets are compressed into MinHash signatures and grouped with locality-sensitive hashing so that only likely matches are compared.

## Sources

* Broder. [On the resemblance and containment of documents](https://doi.org/10.1109/SEQUEN.1997.666900). Compression and Complexity of Sequences, 1997.
* Broder, Glassman, Manasse, and Zweig. [Syntactic clustering of the web](https://doi.org/10.1016/S0169-7552%2897%2900031-7). Computer Networks and ISDN Systems, 1997.
* Indyk and Motwani. [Approximate nearest neighbors: towards removing the curse of dimensionality](https://doi.org/10.1145/276698.276876). STOC, 1998.
* Leskovec, Rajaraman, and Ullman. [Mining of Massive Datasets, chapter 3: finding similar items](http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf).
* Guha, Mishra, Roy, and Schrijvers. [Robust random cut forest based anomaly detection on streams](https://proceedings.mlr.press/v48/guha16.pdf). ICML, 2016.
* Lee, Ippolito, Nystrom, Zhang, Eck, Callison-Burch, and Carlini. [Deduplicating training data makes language models better](https://arxiv.org/abs/2107.06499). 2022.
* Telnyx. [Embeddings API](https://telnyx.com/products/embeddings-api).

Share on Social

## Jump to:

[What is a shingle?](#what-is-a-shingle)[How does shingling measure document similarity?](#how-does-shingling-measure-document-similarity)[How to choose the shingle size k](#how-to-choose-the-shingle-size-k)[Shingling at scale: MinHash and locality-sensitive hashing](#shingling-at-scale-minhash-and-locality-sensitive-hashing)[Shingling numeric sequences and data streams](#shingling-numeric-sequences-and-data-streams)[Shingling vs embeddings](#shingling-vs-embeddings)[Example: k-shingles and Jaccard similarity in Python](#example-k-shingles-and-jaccard-similarity-in-python)[Frequently asked questions](#frequently-asked-questions)[Sources](#sources)

## Sign up for emails of our latest articles and news

What is shingling? k-shingles, MinHash, and Jaccard similarity