A MapReduce-based Filtering Algorithm for Vector Similarity Join

Information

Title A MapReduce-based Filtering Algorithm for Vector Similarity Join
Authors Byoungju Yang, Jaeseok Myung, Sang-goo Lee, Dongjoo Lee
Year 2013 / 1
Keywords Vector Similarity Join, Prefix Filtering, MapReduce Algorithm
Acknowledgement NRF
Publication Type International Conference
Publication Proceedings of the 7th International Conference on Ubiquitous Information and Communication 2013 (ICUIMC 2013)

Abstract

Vector Similarity Join is a fundamental operation that is utilized in data cleaning and analysis. Since most objects can be represented as feature vectors, finding similar pairs of objects is quite an important task. However, Vector Similarity Join is a heavy computational job, because its complexity is proportional to the square of the number of vectors. In order to diminish its computational load, many filtering techniques have been proposed so far. In addition to that, algorithms for distributed systems also have been researched to manage large datasets. But, the state-of-the-art studies also suffer from voluminous computations. In this paper, we propose a MapReduce algorithm that efficiently executes Vector Similarity Join. In the first stage of our algorithm, we use prefix filtering to reduce the number of candidate pairs. The second stage calculates similarities from candidate pairs of the first stage. We present candidates quantity prediction formulas to demonstrate the effiectiveness of our algorithm. Experimental results show that our algorithm outperforms state-of-the-art MapReduce algorithms.