Efficient Snapshot KNN Join Processing for Large Data Using MapReduce
Yupeng Hu, Chong Yang, Cun Ji, Yang Xu, Xueqing Li · 2016
The kNN join problem, denoted by R ×KNNS, is to find the k nearest neighbors from a given dataset S for each point in the query set R. It is an operation required by many big data applications. As large volume of data are continuously generated in more and more real-life cases, we address the problem of monitoring kNN join results on data streams. Specifically, we are concerned with answering kNN join periodically at each snapshot which is called snapshot kNN join. Existing kNN join solutions mainly solve the problem on static datasets, or on a single centralized machine, which are difficult to scale to large data on data streams. In this paper, we propose to incrementally calculate the kNN join results of time tifrom the results of snapshot ti-1. Typically, for the data continuously generated on the data stream, we can get Si= Si-1+ ΔSifor the valid datasets of adjacent snapshots, where ΔSidenotes the updated points between time ti-1and ti. Our basic idea is to first find the queries in R whose kNN results can be affected by the updated points in ΔSi, and then update the kNN results of these small part of queries respectively. In this way, we can avoid calculating the kNN join results on the whole dataset Siin time ti. We propose an implementation of searching for affected query points in MapReduce to scale to large volume of data. In brief, the mappers partition the datasets into groups, and the reducers search for affected queries separately on each group of points. Furthermore, we present the enhanced strategies of data partitioning and grouping to reduce the shuffling cost and computational cost. Extensive experiments on real-world datasets demonstrate that proposed methods are efficient, robust, and scalable.