Approximate String Joins in a Database (Almost) for Free

By Luis Gravano, Panagiotis G. Ipeirotis, Hosagrahar Visvesvaraya Jagadish, Nick Koudas, S. Muthu Muthukrishnan, Divesh Srivastava. Very Large Data Bases Conference, 2001

638 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/5737a1f6fd8d928b88726ada916d7874afdfe0d7

How researchers see this paper

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

Citations in the corpus

A Comparison of Personal Name Matching: Techniques and Practical Issues (2006, methodology): “Pattern matching techniques are commonly used in approximate string matching [15, 17, 22], which has widespread applications, from data linkage [5, 6, 28, 30, 31, 32] and duplicate detection [2, 3, 9], information retrieval [13, 18], correction of spelling errors [10, 19, 27], approximate database j”
Interactive deduplication using active learning (2002, methodology): “Such ideas have been used earlier in [19, 11 , 5]”
Efficient Merging and Filtering Algorithms for Approximate String Searches (2008, methodology): “, [3], [4]) have been proposed for answering approximate string queries efficiently.”
On indexing error-tolerant set containment (2010, background): “For example, edit distance can be indexed by building an index over the set of q-grams of a string [17].”
Duplicate Record Detection: A Survey (2007, background): “Gravano et al. [45] propose using the string lengths and the number of common q -grams of two strings as canopies (filters according to [45]) for the edit distance metric, which is expensive to compute in a relational database.”
Efficient similarity joins for near duplicate detection (2008, methodology): “For text documents, edit distance [26] and Jaccard similarity on q-grams [17] are commonly used.”
Robust and fast similarity search for moving object trajectories (2005, background): “Q-grams have been well studied as a solution to the approximate string matching problem [17, 31, 10], which is defined as follows: given a long text of length n and a pattern of length m (m ≤ n), retrieve all the segments of the text whose edit distance to the pattern is at most k.”
Data Matching (2012, methodology): “Various techniques have been developed that facilitate similarity joins within database environments [22, 127, 170, 232, 272, 289].”
A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication (2012, methodology): “A large amount of work has also been conducted by the database community on similarity joins [42], [51], [56], [57], [58], [59], where the aim is to facilitate efficient and scalable approximate joins for similarity measures such as edit or Jaccard distance.”
Efficient parallel set-similarity joins using MapReduce (2010, methodology): “The techniques described in this paper can also be used for approximate string search using the edit or Levenshtein distance [13].”
A Primitive Operator for Similarity Joins in Data Cleaning (2006, methodology): “Custom join algorithms for particular similarity functions have been proposed for edit distance [9] and for co-sine similarity [8, 6].”