Efficient parallel set-similarity joins using MapReduce
By Rares Vernica, Michael J. Carey. SIGMOD Conference, 2010
525 citations recorded by the source corpus.
In this paper we study how to efficiently perform set-similarity joins in parallel using the popular MapReduce framework. We propose a 3-stage approach for end-to-end set-similarity joins. We take as input a set of records and output a set of joined records based on a set-similarity condition. We efficiently partition the data across nodes in order to balance the workload and minimize the need for replication. We study both self-join and R-S join cases, and show how to carefully control the amount of data kept in main memory on each node. We also propose solutions for the case where, even if we use the most fine-grained partitioning, the data still does not fit in the main memory of a node. We report results from extensive experiments on real datasets, synthetically increased in size, to evaluate the speedup and scaleup properties of the proposed algorithms using Hadoop.
Subfields: Computer Networks and Communications, Management Science and Operations Research, Signal Processing
View Paper: https://www.semanticscholar.org/paper/e7c265f5d8d7c748b3be29515b70e8b20dd7a0f4
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 Management Science and Operations Research
In Signal Processing
Citations in the corpus
- Trends in Cleaning Relational Data: Consistency and Deduplication (2015, methodology): “There are also techniques that balance the workload of comparing all record pairs by exploiting the properties of the similarity measure used for comparing two record [97, 110].”
- Efficient Processing of k Nearest Neighbor Joins using MapReduce (2012, methodology): “In [16, 13], they study how to perform set-similarity join in parallel using MapReduce.”
- Hyracks: A flexible and extensible foundation for data-intensive computing (2011, methodology): “We observe that the Hyracks job scales linearly with growing data size since all operations in the pipeline have linear computational complexity for the memory and data sizes considered here.”
- Efficient k-nearest neighbor graph construction for generic similarity measures (2011, methodology): “Inthe text retrieval community, efficient methods based on prefix-filtering are developed for the ǫ -NN graph construction [2, 22, 21], a different kind of nearest neighbor graph which establishes an edge between all pairs of points whose similarity is above ǫ .”