On the resemblance and containment of documents

By Andrei Z. Broder. 1997

Subfields: Information Retrieval & Search

How researchers see this paper

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

In Information Retrieval & Search

Citations in the corpus

Deduplicating Training Data Makes Language Models Better (2021, methodology): “Approximate full document matching uses hashbased techniques (Broder, 1997) to identify pairs”
The RefinedWeb Dataset for Falcon LLM: Outperforming Curated Corpora with Web Data, and Web Data Only (2023, methodology): “Because Biderman et al. (2023) uses the MinHash settings from Lee et al. (2022), they are mostly identical to ours.”
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “Utilizing minwise hashing [2, 15], which is the LSH for resemblance and is known to outperform SRP in sparse data [23], we can construct an even better ALSH (i.”
Data Portraits: Recording Foundation Model Training Data (2023, methodology): “GPT-3 and other LLMs ([25, 23] among others) use the MinHash sketch of Broder [6] to deduplicate their training sets.”
From Frequency to Meaning: Vector Space Models of Semantics (2010, methodology): “Definitions of LSH functions include the Min-wise independent function, which preserves the Jaccard similarity between vectors (Broder, 1997), and functions that preserve the cosine similarity between vectors (Charikar, 2002).”
Distributed Simulation and Distributed Inference (2018, neutral): “Starting with the works of Gács and Körner [GK73] and Wyner [Wyn75], these include among others correlated sampling [Bro97, KT02, Hol07, BGH + 16], where two players with shared randomness, and given the explicit description of two distributions p , q need to output, without communicating, samples…”
RUPEE: A fast and accurate purely geometric protein structure search (2018, methodology): “130 We have adapted the syntactic approach to document similarity, often referred to as 131 shingling [23], to our linear encoding of protein structure.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “On a related front, the authors of [13, 14] considered similarity search between sets (say A,B) using the Jaccard coefficient s(A,B) = |A∩B|/|A∪B|.”
Counterfactual Memorization in Neural Language Models (2021, methodology): “Following the method from [Lee et al., 2021], we first use MinHash [Broder, 1997] to identify near-duplicate examples in RealNews train set.”
Measuring Forgetting of Memorized Training Examples (2022, methodology): “We deduplicated C4 with the MinHash strategy introduced by [6] and the implementation and parameters from [51].”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “Starting with [25] and [47] where the problem of generating shared randomness from correlated randomness and vice-versa, respectively, were considered, several important variants have been studied such as correlated sampling [11], [16], [34], [38] and noninteractive simulation [20], [27], [36].”
Towards the Semantic Web: Collaborative Tag Suggestions (2006, background): “6 Tag Normalization Collapsing syntactic variances of the same term can fit i the same algorithmic framework, for instance, by computing the bi-grams (shingles of two characters [1]) of the tags in the currently chosen tag set C.”
Efficient similarity joins for near duplicate detection (2008, methodology): “Several synopsis-based schemes have been proposed and widely adopted [5, 7, 10].”
On indexing error-tolerant set containment (2010, background): “Motivated by the above limitation, asymmetric notions of set-based similarity have been proposed in prior work [8, 10].”
Fast and flexible bacterial genomic epidemiology with PopPUNK (2018, methodology): “To calculate p core and p accessory , comparisons were run using the MinHash algorithm (Broder 1997) as implemented in Mash (Ondov et al. 2016) , which estimates the Jaccard similarity between reduced size k -mer ‘sketches’ of the two sequences.”
Cross-architecture bug search in binary executables (2015, methodology): “We chose to use MinHash [5], which satisfies the LSH properties and at the same time converges against the Jaccard index.”
Efficient set joins on similarity predicates (2004, background): “…the intersect size to union size is greater than a fraction f. Weighted match > T where elements are attached with arbitrary weights (for example, inverse of their frequency in the database) and the goal is to .nd all set pairs where the total weight of the common/overlapping elements is > T .”