Given two object sets Q and O , a metric similarity join finds similar object pairs according to a certain criterion. This operation has a wide variety of applications in data cleaning, data mining, to name but a few. However, the rapidly growing volume of data nowadays challenges traditional metric similarity join methods, and thus, a distributed method is required. In this paper, we adopt a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure the load balancing, we present two sampling based partition methods. One utilizes the pivot and the space-filling curve mappings to cluster the data into one-dimensional space, and then selects high quality centroids to enable equal-sized partitions. The other uses the KD-tree partitioning technique to equally divide the data after the pivot mapping. To avoid unnecessary object pair evaluation, we propose a framework that maps the two involved object sets in order, where the range-object filtering, the double-pivot filtering, the pivot filtering, and the plane sweeping techniques are utilized for pruning. Extensive experiments with both real and synthetic data sets demonstrate that our solutions outperform significantly existing state-of-the-art competitors.
Algorithm, Similarity Joins, Metric Space, MapReduce
Computer Sciences | Databases and Information Systems | Theory and Algorithms
Data Management and Analytics
IEEE Transactions on Knowledge and Data Engineering
Institute of Electrical and Electronics Engineers (IEEE)
GAO, Yunjun; YANG, Keyu; CHEN, Lu; ZHENG, Baihua; CHEN, Gang; and CHEN, Chun.
Metric similarity joins using MapReduce. (2017). IEEE Transactions on Knowledge and Data Engineering. 29, (3), 656-669. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3323
Copyright Owner and License
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.