Identifying and Filtering Near-Duplicate Documents

By Andrei Z. Broder. 2000

495 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

StarCoder: may the source be with you! (2023, methodology): “We followed the deduplication pipeline from Ben Allal et al. (2023), which consists of calculating the MinHashes (Broder, 2000) of all source code ﬁles, followed by Locally Sensitive Hashing (LSH) to map similar code ﬁles to the same bucket.”
SantaCoder: don't reach for the stars! (2023, methodology): “Their near-deduplication pipeline largely inherited the settings from CodeParrot (Tunstall et al., 2022): MinHash (Broder, 2000) + Locality Sensitive Hashing (LSH) based on datasketch 9 with unigrams (non-alphanumeric tokens) and a 0 .”
The Stack: 3 TB of permissively licensed source code (2022, methodology): “Next, we compute the MinHash with 256 permutations of all documents, and use Locality Sensitive Hashing (Har-Peled et al., 2012) to find clusters of duplicates.”
Difference engine (2008, unknown): “Broder adapted Manber’s approach to the problem of identifying documents (in this case, Web pages) that are nearly identical using a combination of Rabin fingerprints and sampling based on minimum values under a set of random permutations [8].”
Synthetic review spamming and defense (2013, background): “Examples include the detection of duplicate or near-duplicate documents [20, 3], and phrase-level duplication [7].”
External validity of sentiment mining reports: Can current methods identify demographic biases, event biases, and manipulation of reviews? (2014, methodology): “• Near-duplicates: The detection of near duplicates is done using a shingle method [88], which splits a document into different n-gram features—fingerprints of the document.”
Information Retrieval for E-Discovery (2013, background): “Perhaps the best known is shingling, the use of overlapping subsets, to detect duplicate Web pages (which are pages that share exact duplicates of many subsets) [27].”
BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions (2024, methodology): “To conclude the best practice, We will explore the evaluation results with multiple approaches like manual selection, hash-based deduplication [13] and LLM-based decontamination [65].”
Detecting duplicate web documents using clickthrough data (2011, methodology): “One of the commonly used methods for detecting near duplicates is based on shingling [5, 7].”
Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement (2024, methodology): “Subsequently, deduplication techniques, including MinHash (Broder, 2000), are employed to filter out similar mathematical documents.”
Efficient semi-streaming algorithms for local triangle counting in massive graphs (2008, methodology): “In the next section, we revisit the general technique [8, 9, 6, 7] to estimate the Jaccard coefficient and thus the size of the intersection of two sets A and B, defined over the same Table 1: Datasets used in the experiments.”
Semantic Matching in Search (2014, background): “Other tasks in information retrieval and natural language processing also rely on semantic matching, such as paraphrasing & textual entailment [62, 54], question answering [21], cross-language information retrieval (CLIR) [141, 140], online advertising [31], similar document detection [32, 33], and ”
A Comprehensive Study of the Past, Present, and Future of Data Deduplication (2016, methodology): “[119] is based on Broder’s theorem [115] [see (7) in Section III-C]: deterministically sampling several Rabin”
Large Scale Parallel Document Mining for Machine Translation (2010, result): “…avoid the prohibitive quadratic computational complexity of the naive approach of performing a comparison of every possible pair of input documents is similar to previous work in near duplicate detection (Broder, 2000; Henzinger, 2006; Manber, 1994) and noisy data retrieval (Harding et al., 1997).”
An Evaluation Framework for Plagiarism Detection (2010, background): “The rationale of this setup is as follows: a well-known fact from near-duplicate detection is that if two documents share only a few 8-grams—so-called shingles—it is highly probable that they are duplicates [5].”
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007, background): “Other applications of cardinality estimators include data mining of massive data sets of sorts—natural language texts [4, 5], biological data [17, 18], very large structured databases, or the internet graph, where the authors of [22] report computational gains by a factor of 500 attained by probabil”
Effective and Fast Near Duplicate Detection via Signature-Based Compression Metrics (2016, background): “To improve the efficiency, the use of super shingles was later proposed to deal with large collections [20].”