Evidlake
Menu

Near-duplicate Detection

Also known as: deduplication, shingling, MinHash, SimHash, 近重复检测.

Finding documents that are almost, but not exactly, the same, such as a news story republished with a new headline, by comparing fingerprints of their word sequences.

Updated Last reviewed

Synthetic dataExamples on this page use synthetic data created for illustration.

Definition

Near-duplicate detection finds documents that are almost, but not exactly, the same, such as a news story republished with a new headline. Methods turn each text into a compact fingerprint of its word sequences and call two documents near-duplicates when their fingerprints overlap enough.

In plain terms

An exact hash fails the moment one word differs. The standard approach cuts each text into overlapping runs of words called shingles, then measures how much two sets of shingles overlap (the Jaccard similarity: shared shingles divided by all distinct shingles). Techniques such as MinHash and SimHash compress those sets so that millions of documents can be compared quickly.

The aim is to count stories, not copies. Two independent reports of the same event are not duplicates: they share facts but not wording. Keep the original documents and record which cluster each belongs to.

Example

Word 3-shingles (every run of three consecutive words):

TextShinglesShared with AJaccard similarity to A
A: “the central bank raised rates on tuesday”5——
B: “the central bank raised rates on tuesday morning”655 / 6 = 0.83
C: “policymakers lifted the benchmark rate on tuesday”500 / 10 = 0

B is a near-duplicate of A (one added word); C reports the same event in different words and is correctly kept as a separate story.

Common misunderstandings

  • “Two stories about the same event are duplicates.” Duplicates share wording; independent reports share facts.
  • “An exact checksum is enough.” One changed word or a new headline defeats it.
  • “One similarity threshold suits all text.” Short items and boilerplate-heavy pages need different settings; check examples.
  • Mention Volume

    How many times a topic, brand or person is mentioned in a defined set of sources over a period. Its meaning depends entirely on how the count is defined.

  • Syndicated Content

    Material produced once and published by many outlets, such as a news-agency story. Counting every publication overstates how many independent sources reported something.

  • Tokenization

    Splitting text into the units a search or analysis system works with, usually words. It decides what can match, and in Chinese finding the word boundaries is a task of its own.

References

  1. Andrei Z. Broder. On the Resemblance and Containment of Documents . Proceedings of Compression and Complexity of SEQUENCES 1997, 1997. DOI: 10.1109/SEQUEN.1997.666900
  2. Gurmeet Singh Manku, Arvind Jain, Anish Das Sarma. Detecting Near-duplicates for Web Crawling . Proceedings of the 16th International Conference on World Wide Web, 2007. DOI: 10.1145/1242572.1242592
  3. Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze. Near-duplicates and shingling, in Introduction to Information Retrieval . Cambridge University Press, 2008.