Parallel Top-k Join on Massive High-Dimensional Vectors
You Ma · Chinese Journal of Computers · 2015
Top-k joins on high-dimensional vectors are very important operations in many applications.Given two vector sets Rand S,a Top-kjoin returns k closest pairs of vectors.The traditional centralized algorithms cannot deal with the large scale high-dimensional vectors in an efficient way.MapReduce,as a parallel processing framework,can deal with large scale data set.It has been widely used in many applications because of its high availability and high scalability.In this paper we adopt Piecewise Aggregate Approximation technique(PAA)to reduce the dimensionality of the vectors;then group the vectors using Symbolic Aggregate Approximation technique(SAX);based on the MapReduce framework,we propose SAX-based parallel Top-k join query algorithms.The experiments results show that the proposed approaches have better performance and scalability.