A Primitive Operator for Similarity Joins in Data Cleaning

By Surajit Chaudhuri, Venkatesh Ganti, Raghav Kaushik. 2006

631 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems, Management Science and Operations Research, 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 Artificial Intelligence

In Information Systems

In Management Science and Operations Research

In Information Retrieval & Search

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, background): “This generalization comes with no cost and the extended framework inherits all the theoretical guarantees of LSH.”
SourcererCC: Scaling Code Clone Detection to Big-Code (2015, background): “Formally, it can be stated in the form of a following property [7]: Property 1: Given blocks Bx and By consisting of t tokens”
Mining of Massive Datasets (2011, methodology): “Then N = 3, SUM = [18,−1], and SUMSQ = [110, 5].”
Efficient parallel set-similarity joins using MapReduce (2010, background): “Set-similarity joins on a single machine have been widely studied in the literature [23, 6, 3, 4, 29].”
Efficient Merging and Filtering Algorithms for Approximate String Searches (2008, methodology): “Filtering: If two strings s, and S2 are within edit distance k, the difference between their lengths cannot exceed k.”
Mining Document Collections to Facilitate Accurate Approximate Entity Matching (2009, methodology): “As discussed earlier in Section 1, string similarity functions have been used for identifying substrings from documents that approximately match with some dictionary entry ( e.g. , [9]), and for identifying pairs of matching records ( e.g. , [10, 11]).”
CrowdER: Crowdsourcing Entity Resolution (2012, methodology): “Since it is expensive to compute the similarity for every pair of records, research on similarity-based techniques [2, 5,26] mainly focuses on how to reduce the number of pairs evaluated.”
Efficient exact set-similarity joins (2006, methodology): “In contrast, previous algorithms [6, 22] do not provide any such guarantee.”
On indexing error-tolerant set containment (2010, methodology): “Motivated by the above limitation, asymmetric notions of set-based similarity have been proposed in prior work [8, 10].”
Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, methodology): “To counter the often unnecessary penalization of the sizes of the sets with resemblance, a modified measure, the set containment (or Jaccard containment) was adopted [6, 1, 11].”
Asymmetric Minwise Hashing (2014, methodology): “While the resemblance similarity is convenient and useful in numerous applications, there are also many scenarios where the resemblance is not the desirable similarity measure [1, 11].”
b-Bit Minwise Hashing for Estimating Three-Way Similarities (2010, background): “The efficient computation of the similarity (or overlap) between sets is a central operation in a variety of applications, such as word associations (e.g., [13]), data cleaning (e.g., [40, 9 ]), data mining (e.g., [14]), selectivity estimation (e.g., [30]) or duplicate document detection [3, 4]. In”
Efficient similarity joins for near duplicate detection (2008, methodology): “Recent advances include inverted index-based methods [24], prefix filtering-based methods [8, 3] and signature-based methods [1].”