METRIC KNN JOINS USING SPARK

Abstract

k nearest neighbor join(kNN Join) refers to finding the k nearest neighbor vectors in another data set R for each object in the data set S by using the nearest neighbor formula and the distance calculation formula between vectors in two data sets.kNN Join has a wide range of applications, so it has received attention.However, as a combination of k nearest neighbor join queries and join calculations, processing kNN joins of high dimensional data is quite time consuming.To handle larger data sets, the Hadoop and Spark frameworks have been the tool of choice for parallel and distributed computing in recent years.In this paper, we present the vertical decomposition data for processing kNN connections using Spark.We propose to first approximate the vector piecewise aggregatio and the symbol aggregation approximation SAX, then decompose the vector vertically to satisfy the distributed operation, calculate the distance between different vectors in each partition, and then merge the partitions to meet the conditions. Calculate the vector and finally find the true distance between the vectors.The specific process is described in the implementation section of the text. The experimental results show that the proposed method improves the computational speed under the premise of ensuring the accuracy of the experimental results.