Near-Duplicate Detection: Shingles, MinHash, SimHash and LSH at Scale

Readers scroll past the same news six times and stop trusting the feed. Near duplicate detection is the step that spots these copies, even when every copy differs a little from the others.

Picture a common setup. A news app in India pulls about 2 lakh (200,000) articles a day from 300 publishers, and keeps an archive of 1 crore (10 million) articles. The setup is made up, but the problem is real.

One news agency story about heavy rain in coastal Karnataka reaches the app from six sites. One adds "Also read" links. Another changes the headline and one word in the body. A third copies it with different spacing and capital letters.

To a computer, these are six different documents. The app needs to show one card and keep the others as alternate sources. The rest of this guide builds that step, from the simplest check to a pipeline that handles the full archive.

You need seven words. Each one is tied to the rain story.

• Document: one piece of text you want to compare, here one article body.
• Set: a collection where each item counts once. Two documents become two sets of word runs.
• Hash: a function that turns any text into a fixed-size number. The same text always gives the same number.
• Shingle: a run of k words in a row. With k = 3, "heavy rain is likely" gives "heavy rain is" and "rain is likely".
• Jaccard similarity: shared shingles divided by all distinct shingles in either document. It runs from 0 to 1.
• Signature or fingerprint: a small summary of a document, built from hashes, that you compare instead of the full text.
• Candidate pair: two documents that a fast filter says might be near-duplicates. A slower exact check confirms or rejects them.

Near duplicate detection is a pipeline. It turns each document into a set of shingles, compresses that set into a small signature, and uses signatures to find and confirm pairs above a similarity threshold.

The point is to avoid comparing every document with every other one. For 1 crore articles that is 49,999,995,000,000 pairs, about 50 lakh crore (50 trillion). At the 47 microseconds per pair our exact check took, that is about 75 years on one core.

The pipeline below is what the rest of this guide builds and tests. Each stage throws away work the next stage would waste time on.

Two families of signatures exist. MinHash goes back to Andrei Broder's 1997 paper on resemblance and containment, and estimates Jaccard similarity. SimHash builds on Moses Charikar's 2002 paper and gives one fingerprint where similar documents tend to differ in few bits, especially long ones.

An exact hash catches only perfect copies, and checking all pairs is far too slow. Most teams try both first, so it helps to see each fail on the rain story.

The naive exact hash

The naive first try is to hash each article and drop repeats. Normalising first, meaning lower case and single spaces, does catch the copy with different spacing and capitals. That is worth keeping as a cheap first pass.

But change one word and the hash changes completely, because a good hash is designed to look random. The copy that says "Sunday evening" instead of "Sunday" sails through. So does the one with "Also read" links.

In our test pipeline of 1,20,000 (120,000) synthetic articles, the exact pass removed 6,667 copies that differed only in case and spacing. It found none of the 13,333 edited copies.

The naive all-pairs check

The second naive try is to compute Jaccard similarity for every pair. That is correct, but the pair count grows with the square of the archive. Even 1,20,000 articles make 7,199,940,000 pairs.

Near duplicate detection fixes both problems. Shingles make small edits cause small changes, and signatures with LSH make most pairs never get compared.

Slide a window of k words across the text and keep each window as one item in a set. A one-word edit then changes only the k shingles that cover that word, and every other shingle still matches.

Here is the idea on two short sentences that differ in one word. It is plain Python with no libraries.

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)

x = "the monsoon session of parliament begins on monday with a debate on the data bill"
y = "the monsoon session of parliament begins on tuesday with a debate on the data bill"
sx, sy = shingles(x), shingles(y)
print(len(sx), len(sy), len(sx & sy))  # shingles in x, in y, shared
print(round(jaccard(sx, sy), 3))

It prints 13 13 10, then 0.625. Each sentence has 13 three-word shingles. Changing "monday" to "tuesday" breaks the 3 shingles that contain it, so 10 are shared out of 16 distinct ones.

Choosing the shingle size k

Small k makes unrelated documents look alike, and large k makes small edits look big. We measured both effects on synthetic 300-word articles built from real English words, with 200 trials per cell.

With single words, unrelated articles scored 0.239, because common words like "the" and "of" appear everywhere. With k = 5, unrelated pairs fell to about 0.001, while one changed word still left 0.967.

The arithmetic explains the 10-word column. A 300-word article has 296 five-word shingles. Ten scattered edits break up to 50 of them and create up to 50 new ones, so Jaccard is about 246 out of 346, or 0.71.

So "97 percent of the words are the same" can mean a Jaccard of 0.73. Keep that gap in mind when you pick a threshold later.

The Mining of Massive Datasets course slides give the same caveat: pick k large enough, or most documents will have most shingles. For very short text such as titles, word shingles are too few. Character shingles, runs of characters instead of words, give more items to compare.

MinHash applies the same random hash function to every shingle of both documents and keeps only the smallest value from each. With an ideal random hash, the chance the two smallest values match equals the Jaccard similarity.

Repeat that with 128 different hash functions and the share of matches is a good estimate. Why does it work? Imagine mixing both shingle sets together and picking the one with the smallest hash. Every shingle is equally likely to be picked. Pick one that sits in both documents, and the two minimums match.

The chance of picking a shared shingle is shared shingles divided by all distinct shingles. That is the Jaccard similarity. Broder's paper proves this for random permutations, which here means randomly reordering all possible shingles.

The wedding guest list picture

Think of two families planning one joint wedding reception, each with its own guest list. The shared guests are the shingles both documents have.

• Each family's guest list is one document's set of shingles.
• A lucky draw that shuffles every name on both lists is one hash function.
• The first name drawn from each family's own list is that document's minimum.
• Both families get the same first name only when the overall first name is a shared guest.
• Running 128 separate draws and counting matches is the MinHash signature comparison.

Where the picture breaks: a real hash function is not a perfect shuffle. As the next test shows, a weak one can quietly push every estimate upwards.

MinHash in NumPy

This version uses 128 hash functions of the form a times x plus b, keeping the top 32 bits. NumPy, the Python library for fast number arrays, does all 128 at once. We ran it on NumPy 2.5.4.

import hashlib
import numpy as np

def shingle_ids(text, k=3):
    """Hash each k-word shingle to a 64-bit number."""
    words = text.lower().split()
    ids = {int.from_bytes(hashlib.blake2b(" ".join(words[i:i + k]).encode(),
                                          digest_size=8).digest(), "little")
           for i in range(len(words) - k + 1)}
    return np.fromiter(ids, dtype=np.uint64)

def make_hashes(n=128, seed=7):
    """n hash functions h(x) = top 32 bits of (a*x + b), a odd, wrapping at 2**64."""
    rng = np.random.default_rng(seed)
    a = rng.integers(0, 2**63, size=n, dtype=np.uint64) * np.uint64(2) + np.uint64(1)
    b = rng.integers(0, 2**63, size=n, dtype=np.uint64)
    return a, b

def minhash(ids, a, b):
    with np.errstate(over="ignore"):
        h = np.right_shift(np.outer(a, ids) + b[:, None], np.uint64(32))
    return h.min(axis=1)  # one minimum per hash function

x = "the monsoon session of parliament begins on monday with a debate on the data bill"
y = "the monsoon session of parliament begins on tuesday with a debate on the data bill"
a, b = make_hashes()
sx, sy = minhash(shingle_ids(x), a, b), minhash(shingle_ids(y), a, b)
print(sx.shape, round(float(np.mean(sx == sy)), 3))

It prints (128,) 0.609. The signature is 128 numbers, and 61 percent of positions match, against a true Jaccard of 0.625. Short texts give noisy estimates, which the next table measures.

Our first version used a weaker formula, a times x plus b modulo a large prime, with numbers too small to mix well. Across 300 seeds it estimated 0.558 for a pair whose true Jaccard was 0.462.

The draws were lopsided. The 5 smallest of 296 shingle numbers won 20 percent of the 128 draws, against about 2 percent for a fair hash. The fixed version above averaged 0.463.

How many hash functions do you need?

The error shrinks with the square root of the number of hash functions: four times the functions gives half the error. For one pair with true Jaccard 0.462, we repeated the estimate with 300 different random seeds. We also ran datasketch 2.0.0, an open-source Python library for MinHash and LSH.

Std is the standard deviation, the typical distance of an estimate from its average. At 128 hash functions, most estimates land within about 0.09 of the truth, two standard deviations. That is fine for finding candidates, which you then check exactly.

The sizes assume datasketch's default storage in version 2.0.0: 4 bytes per value. The datasketch MinHash docs put the sampling error of a 128-value signature at about 0.03 to 0.04. Our 0.044 sits at the top of that band, because pairs near 0.5 are the noisiest.

Beginners can stop here: you know what a near-duplicate is, how shingles and Jaccard measure it, and how MinHash makes it cheap. The rest covers finding pairs at scale, thresholds, SimHash and a full pipeline.

LSH banding cuts each 128-number signature into b bands of r numbers and hashes each band into a bucket. Two documents become a candidate pair if any one band lands in the same bucket.

A pair with Jaccard s matches one whole band with chance s to the power r. It misses all b bands with chance one minus that, to the power b. So the chance of becoming a candidate is 1 minus (1 minus s to the r) to the b.

Plot that chance against s and you get an S-shaped curve. Below the bend almost nothing becomes a candidate; above it almost everything does. Choosing b and r moves the bend.

def candidate_chance(s, b, r):
    """Chance that a pair with Jaccard s matches in at least one of b bands of r rows."""
    return 1 - (1 - s ** r) ** b

for s in (0.5, 0.7, 0.8, 0.9):
    print(s, round(candidate_chance(s, b=16, r=8), 3), round(candidate_chance(s, b=9, r=13), 3))

It prints four rows. With 16 bands of 8, a pair at 0.8 becomes a candidate with chance 0.947. With 9 bands of 13, the same pair gets only 0.399.

We checked the formula with datasketch's MinHashLSH index. With 16 bands of 8, pairs averaging Jaccard 0.628 became candidates 36 percent of the time; the formula predicted 33 percent.

The Mining of Massive Datasets slides work the classic case of 20 bands of 5 rows. A pair at 0.8 is found 99.965 percent of the time, while a pair at 0.3 slips through about 4.74 percent of the time.

Pick the threshold from labelled examples of your own data, then choose bands that catch pairs at that threshold, and confirm every candidate with an exact check. The threshold is a product decision first and a maths decision second.

For the news app, two articles that differ only in a headline and an "Also read" line are duplicates. Two articles about the same rain, written separately, are not. Separately written articles share some phrases, but far fewer 5-word runs than a copy does. A labelled sample, described below, shows where the line sits for your data.

The datasketch threshold is soft

datasketch's MinHashLSH takes a threshold argument and picks b and r for you. Its source code tries every pair of b and r. It keeps the pair with the smallest area of false positives below the threshold plus false negatives above it, weighted equally by default.

Pause and predict: you build the index with threshold=0.8 and 128 hash functions. What share of true pairs with Jaccard between 0.80 and 0.85 will a query return? A natural guess is almost all of them.

In our 1,20,000-article run, it returned 56.6 percent of the 2,020 such pairs. Across all pairs at 0.8 or above, recall was 79.5 percent. Recall is the share of true pairs you actually find.

What just happened? datasketch chose 9 bands of 13 rows, whose curve crosses one half at about 0.82. A pair sitting exactly at the threshold has only about a 40 percent chance of being returned.

The datasketch LSH docs say this plainly: the curve is a soft threshold, and sets slightly above it are occasionally missed. Our run shows how large "occasionally" can be when many pairs sit near the line.

Setting the curve's bend below your real threshold cost about 2,800 extra candidate checks and bought back almost all the missed pairs. Each exact check took microseconds; the whole verify step took 0.39 seconds.

You can do this two ways. Pass params=(16, 8) to pin the bands yourself, or pass weights=(0.3, 0.7) to make misses count more. With 128 values and threshold 0.8, those weights gave 11 bands of 11 rows. That curve still returns only 63 percent of pairs at exactly 0.8, so print the curve before trusting it.

A threshold-setting procedure

1. 1

   Sample pairs at every level

   Take 200 candidate pairs spread across Jaccard 0.5 to 1.0 from your own data. Use a loose index, such as 32 bands of 4, to find them.

2. 2

   Label them by hand

   Mark each pair duplicate or not, using your product's rule. For the news app, the rule is whether a reader would call it the same story.

3. 3

   Read off the threshold

   Find the Jaccard value where labels flip from mostly not duplicate to mostly duplicate. That is your threshold.

4. 4

   Choose bands below it

   Pick b and r so the S-curve crosses one half a little under your threshold. Check the chance at the threshold itself is above 0.9.

5. 5

   Always verify candidates

   Confirm every candidate with exact Jaccard on the stored shingles, or with the signature estimate if shingles are too big to keep.

The 2007 web crawling paper by Manku, Jain and Das Sarma did this kind of labelling for SimHash. They found precision and recall both near 0.75 at their chosen setting. Precision is the share of reported pairs that are really duplicates.

SimHash turns a whole document into one 64-bit fingerprint, where near-duplicates differ in only a few bit positions. MinHash keeps 128 separate numbers; SimHash keeps 64 bits, or 8 bytes.

To build it, hash every feature, such as a word or shingle, to 64 bits. For each bit position, add the feature's weight if that bit is 1 and subtract it if it is 0. The sign of each total becomes one bit of the fingerprint.

import hashlib
from collections import Counter

def simhash(text, k=3, bits=64):
    words = text.lower().split()
    features = Counter(" ".join(words[i:i + k]) for i in range(len(words) - k + 1))
    totals = [0] * bits
    for feature, weight in features.items():
        h = int.from_bytes(hashlib.blake2b(feature.encode(), digest_size=8).digest(), "little")
        for i in range(bits):
            totals[i] += weight if (h // 2**i) % 2 else -weight
    # a positive total gives a 1 bit; zero or negative gives a 0 bit
    return sum(2**i for i, t in enumerate(totals) if max(t, 0))

def hamming(x, y):
    return bin(x ^ y).count("1")

x = "the monsoon session of parliament begins on monday with a debate on the data bill"
y = "the monsoon session of parliament begins on tuesday with a debate on the data bill"
z = "the city corporation has started a drive to clear blocked drains before the monsoon"
print(f"{simhash(x):016x}")
print(hamming(simhash(x), simhash(y)), hamming(simhash(x), simhash(z)))

It prints the fingerprint 0ddcdfbea0832796 in hexadecimal, then 11 33. The one-word edit moved the fingerprint 11 bits, and the unrelated sentence moved it 33. Hamming distance is the number of bit positions that differ.

Charikar's paper explains why this works. In the random-hyperplane version, each bit records which side of a random direction a vector falls on. Two vectors agree on one bit with chance 1 minus their angle divided by pi. Similar documents point in similar directions, so they share most bits.

SimHash therefore roughly tracks the angle between feature-count vectors, which is cosine similarity, not Jaccard. On our synthetic articles with 3-word features, the angle formula predicted the mean distance closely: 8.1 bits predicted, 7.8 measured, for 10 changed words.

SimHash is strict on short documents

The 15-word example shows the catch. Every feature counts for a lot in a short text, so one changed word flips many bits. On 300-word articles, we measured how often an edited copy stayed within 3 bits.

• 1 word changed: mean distance 2.3 bits, and 82 percent of copies stayed within 3 bits.
• 3 words changed: mean 4.1 bits, and 39 percent stayed within 3 bits.
• 10 words changed: mean 7.8 bits, and under 2 percent stayed within 3 bits.
• Unrelated articles: mean 26.8 bits, and none came within 3 bits.

On 2,000-word articles, 10 changed words gave a mean of 2.0 bits, and 87 percent stayed within 3. Longer documents dilute each edit, which suits whole web pages.

Feature choice matters as much. When we used single words weighted by count, unrelated synthetic articles sometimes scored 0 bits apart. Every synthetic article draws from one word list, so this is a worst case, but common words can swamp real text too.

Manku and co-authors weighted their features and used standard text cleaning, including stop-word removal, before computing 64-bit SimHash. Stop words are very common words such as "the" and "of".

Split the 64 bits into blocks and index each block exactly. If two fingerprints differ in at most 3 bits, those bits can touch at most 3 blocks, so with 4 or more blocks at least one block matches exactly.

This is the pigeonhole principle, and the tables in Manku and co-authors' paper rest on it. They stored about 8 billion fingerprints and needed to find any within 3 bits of a new one.

We built it on 2 to the 20, or 10,48,576 (1,048,576), random fingerprints. Then we planted 2,000 queries 0 to 3 bits from a stored fingerprint and 1,000 queries exactly 4 bits away.

• 4 tables, one per 16-bit block: every planted query within 3 bits was found, and none at 4 bits. Each query checked 64.9 fingerprints on average and took 0.11 milliseconds.
• 20 tables, as in the paper: blocks of 11, 11, 11, 11, 10 and 10 bits, keyed on every choice of 3 blocks. Each query checked 0.9 fingerprints and took 0.05 milliseconds.
• Brute force with NumPy over all 10,48,576 fingerprints took 4.36 milliseconds per query. It XORs each pair, which marks the differing bits, then counts them.

The trade-off is memory against work per query. Twenty tables hold twenty copies of the index; four tables do more checks per query. The paper's own designs range from 4 to 20 tables for the same reason.

Use MinHash with LSH when you want a tunable Jaccard threshold and can afford about 512 bytes per document. Use SimHash when documents are long, storage per document must be tiny, and you only need very close copies.

For the news app, MinHash wins. Articles are a few hundred words, the team wants copies with edited headlines and extra links, and 1 crore signatures need about 5 GB. The next section builds that.

Run the cheap stages first: an exact hash pass, MinHash signatures computed in parallel, and an LSH index. Then check candidates exactly, group pairs into clusters with union-find (a structure that merges groups, explained below), and keep one document per cluster.

from datasketch import MinHash, MinHashLSH

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

def signature(text):
    m = MinHash(num_perm=128)  # default scheme is "affine32" in datasketch 2.0.0
    m.update_batch([s.encode() for s in shingles(text)])
    return m

base = ("heavy rain is likely over coastal karnataka and goa for the next three days "
        "the weather office said on sunday and fishermen have been advised not to "
        "venture into the sea until thursday as wind speeds may touch 55 kmph "
        "schools in two districts will stay shut on monday officials said")
articles = {
    "agency-001": base,
    "site-a-417": base.replace("sunday", "sunday evening"),
    "site-b-092": base + " also read the full forecast on our weather page",
    "site-c-310": ("the city corporation has started a drive to clear blocked drains "
                   "before the monsoon and residents can report problems on the helpline "
                   "officials said the work will finish by the end of the month"),
}

lsh = MinHashLSH(num_perm=128, params=(16, 8))  # 16 bands of 8 values
sigs = {}
for doc_id, text in articles.items():
    sigs[doc_id] = signature(text)
    print(doc_id, "candidates:", sorted(lsh.query(sigs[doc_id])))
    lsh.insert(doc_id, sigs[doc_id])

for doc_id in ("site-a-417", "site-b-092"):
    print(doc_id, round(sigs["agency-001"].jaccard(sigs[doc_id]), 2),
          round(len(shingles(base) & shingles(articles[doc_id]))
                / len(shingles(base) | shingles(articles[doc_id])), 2))

This runs on datasketch 2.0.0, the latest release as of 27 October 2026. The third article matches both earlier ones; the unrelated drain story matches nothing. It then prints two lines, the estimate then the exact Jaccard: 0.88 and 0.83 for the "Sunday evening" copy, 0.8 and 0.84 for the "Also read" copy. The estimate can land on either side of the truth.

Querying before inserting means each new article is checked only against older ones. That is how a daily job adds today's 2 lakh articles to the existing index.

What our 1,20,000-article run cost

We ran the full pipeline on one machine with 2 CPU cores, using datasketch 2.0.0 and Python 3.13. The articles were synthetic: 1,00,000 originals and 20,000 copies. A third changed only spacing and case, a third had light edits of 1 to 8 words, and a third heavy edits of 30 to 60 words.

• Exact pass: 6,667 copies removed in about 10 seconds.
• Shingling 1,13,333 articles took 29 seconds of plain Python.
• MinHash with 128 values took 90 seconds, about 0.8 milliseconds per article on one core.
• Building the 16-band index took 21 seconds and querying every article took 3.5 seconds.
• Exact checks on 8,238 candidates took 0.39 seconds. Union-find formed 4,118 clusters and removed 5,316 more copies.
• The heavy edits fall well below Jaccard 0.8, so they were kept on purpose. Recall on the 5,987 true pairs at 0.8 or above was 99.2 percent.

Signature work grows with the number of articles, not with its square. At 0.8 milliseconds per article, 1 crore articles need about 8,000 core-seconds, roughly 2.2 hours on one core. That is an estimate from our run, not a measurement. Candidate pairs grow with copies per story: one story copied 1,000 times makes 4,99,500 pairs by itself.

Signatures for 1 crore articles take 1 crore times 512 bytes, which is 5.12 GB. The band tables add more on top, so shard them, meaning split the work by band across machines. Each band's table is independent.

Union-find turns pairs into clusters

Pairs are not enough, because copy A may match B and B may match C. Union-find is a small data structure that tracks groups and merges two groups in one quick step. After all confirmed pairs, each group is one story.

Then pick a keeper per cluster with a rule your product owns. The news app keeps the earliest publish time from the original agency, and shows the rest as alternate sources.

When one document contains another

Jaccard punishes size differences. We pasted a 120-word story into a 1,020-word page; all 116 of the story's shingles were on the page, but Jaccard was only 0.114.

Broder's paper defines containment for this case: shared shingles divided by the shingles of the document you are asking about. For the story inside the page, it was 1.0. datasketch provides MinHashLSHEnsemble, an index built for containment search, when you need to find these.

The release notes say the new default fixes an over-estimation bias on large sets. We hit two errors on 2.0.0: comparing a legacy sketch with an affine32 one, and inserting both into one index.

Start from the product rule for "same", then show the cost problem, then the pipeline. Interviewers want to hear why all-pairs fails and how you would tune and check the filter.

1. 1

   Define a duplicate

   Say what the product treats as the same, such as one news story with a new headline. Pick Jaccard on 5-word shingles as the measure.

2. 2

   Show why naive fails

   An exact hash misses one-word edits. All pairs for 1 crore articles is about 50 trillion comparisons.

3. 3

   Sketch the pipeline

   Normalise, exact hash pass, shingles, 128-value MinHash, LSH bands, exact check on candidates, union-find clusters, one keeper each.

4. 4

   Tune with numbers

   Explain the S-curve, 1 minus (1 minus s to the r) to the b, and say you set its bend below the threshold, then verify.

5. 5

   Cover scale and change

   Signatures are 512 bytes each, so 1 crore is about 5 GB. Shard bands across machines and query before insert for daily batches.

6. 6

   Mention SimHash

   Offer SimHash with block tables when storage must be 8 bytes per document and only very close copies matter.