Voronoi-Based kNN Queries Using K-Means Clustering in MapReduce

Introduction

The k nearest neighbor query (kNN query) is a classical problem that has been extensively studied, due to its many important applications, such as knowledge discovery, data mining, and spatial databases. The k nearest neighbor query (kNN) is a special type of query that is k nearest neighbors from points in S for each query point r in dataset R. The kNN query typically serves as a primitive operation and is widely used in spatial databases. The basic idea of implementing kNN queries is to perform a pairwise computation of distance between each object point in S and each object point in R. The computational complexity of such pairwise calculation is O(|R| × |S|). Then, finding the k nearest neighbors in S for every r in R corresponds to sorting the computational distances, and easily leads to a complexity of |S| × log|S|. Therefore, a lot of research works have been dedicated to improve the efficiency of the kNN queries and reduce the computational complexity of the kNN queries (Jagadish et al. 2005) (Bohm et al. 2004) (Ciaccia et al. 1997) (Yu et al. 2010). With the rapid growth of spatial data, the parallel kNN query has become a challenging task.

MapReduce is a parallel processing framework that uses parallel and distributed patterns to process massive data sets. The MapReduce programming model provides good scalability, flexibility and fault tolerance. MapReduce was first introduced by Google (Dean et al. 2008) and ran on the Hadoop clusters, which is an open source framework. MapReduce provides a programming model to process the large scale data sets, which can be distributed easily. The MapReduce programming framework can install on computational clusters and automatically distribute a work job on clusters of machines. Therefore, MapReduce programming model becomes an ideal framework of processing kNN queries over massive spatial datasets. This chapter proposes a method of parallel kNN queries based on k-means clusters using MapReduce programming model.

Now, lots of researches (Yao et al. 2010) have been devoted to improve the performance of kNN query algorithms. However, all these approaches are performed on a single, centralized server. In single machine, the computational capability and storage are limited, and its efficiency is low. How to perform the kNN query on parallel machines is an important issue in cloud computing environments. ALL the existing work has concentrated on the spatial databases based on the centralized paradigm. Xia et al. (2004) proposed a novel kNN-join algorithm, called the Gorder kNN join method. Gorder is a block nested loop join method that exploits sorting, join scheduling and distance computation filtering and reduction to reduce both I/O and CPU costs. It is simple and yet efficient, and handles high-dimensional data efficiently. However, the system of centralized server will eventually suffer from performance deterioration as the size of the dataset increases. A solution is to consider the parallel query processing in distributed cloud computing environment. However, an efficient parallel kNN queries in MapReduce programming framework are challenging tasks. Firstly, the classical query processing algorithms need to be redesigned in MapReduce programming framework. Second, the strategies of data partitioning and distribution need to be designed also in parallel programming model. For this purpose, we improve previous implementations of kNN queries in MapReduce programming framework, focusing on the different steps involved in Map and Reduce phases.