Efficient set joins on similarity predicates

By Sunita Sarawagi, Alok Kirpal. ACM SIGMOD Conference, 2004

376 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/7cb3cb75a60d4e446d6da43801895c6e98655f90

How researchers see this paper

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

In Computer Networks and Communications

In Information Systems

In Signal Processing

Citations in the corpus

Web-Scale Distributional Similarity and Entity Set Expansion (2009, methodology): “Our optimization strategy follows a generalized sparse-matrix multiplication approach (Sarawagi and Kirpal 2004), which is based on the well-known observation that a scalar product of two vectors depends only on the coordinates for which both vectors have non-zero values.”
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].”
Scaling Up All Pairs Similarity Search (background): “The all-pairs similarity search problem has also been addressed in the database community, where it is known as the similarity join problem [1] [7] [21].”
From Frequency to Meaning: Vector Space Models of Semantics (2010, background): “One optimization strategy is a generalized sparse-matrix multiplication approach (Sarawagi & Kirpal, 2004), which is based on the observation that a scalar product of two vectors depends only on the coordinates for which both vectors have nonzero values.”
A Primitive Operator for Similarity Joins in Data Cleaning (2006, methodology): “overlap can be used effectively to support a variety of similarity functions [13].”
Large-Scale Deduplication with Constraints Using Dedupalog (2009, background): “, efficiently identify pairs of records that are similar to each other on a specified set of attributes [29], [39], [40], [41].”
Duplicate Record Detection: A Survey (2007, methodology): “We examine some of the methods that can be used to reduce the cost of record comparison in Section V-B.”
Efficient exact set-similarity joins (2006, methodology): “In contrast, previous algorithms [6, 22] do not provide any such guarantee.”
Efficient similarity joins for near duplicate detection (2008, methodology): “For example, [24] employs sequential access on short inverted lists but switches to binary search on the α − 1 longest inverted lists.”
Data Matching (2012, neutral): “Various techniques have been developed that facilitate similarity joins within database environments [22, 127, 170, 232, 272, 289].”
On indexing error-tolerant set containment (2010, methodology): “We have the following result [10, 29].”
Frameworks for entity matching: A comparison (2010, background): “For example, it has been shown that there is no universally best string similarity measure [29,50].”
Efficient Merging and Filtering Algorithms for Approximate String Searches (2008, methodology): “Many algorithms [9], [2] mainly focused on "join queries," i.”
A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication (2012, background): “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): “Inverted-list-based algorithms for finding pairs of strings that share a certain number of tokens in common have been proposed in [23].”