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

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

Wei Yan (Liaoning University, China)
DOI: 10.4018/978-1-5225-8446-9.ch011

Abstract

The kNN queries are special type of queries for massive spatial big data. The k-nearest neighbor queries (kNN queries), designed to find k nearest neighbors from a dataset S for every point in another dataset R, are useful tools widely adopted by many applications including knowledge discovery, data mining, and spatial databases. In cloud computing environments, MapReduce programming model is a well-accepted framework for data-intensive application over clusters of computers. This chapter proposes a method of kNN queries based on Voronoi diagram-based partitioning using k-means clusters in MapReduce programming model. Firstly, this chapter proposes a Voronoi diagram-based partitioning approach for massive spatial big data. Then, this chapter presents a k-means clustering approach for the object points based on Voronoi diagram. Furthermore, this chapter proposes a parallel algorithm for processing massive spatial big data using kNN queries based on k-means clusters in MapReduce programming model. Finally, extensive experiments demonstrate the efficiency of the proposed approach.
Chapter Preview
Top

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.

Key Terms in this Chapter

kNN Queries: Given two dataset R and S in space D , and an integer k . k NN queries of R and S (denoted as k nnQ), combine each point r ? R with its k nearest neighbors from S : k nnQ( R , S ) = {( r , k NN( r , S )) | for all r ? R }.

Voronoi Diagram: The Voronoi diagram of a given set P = { p 1 , p 2 , …, p n } of n points in R d partitions the space of R d into n regions. Each region includes all points in R d with a common closest point in the given set P using the distance metric Dist (). The region corresponding to the point p ? P contains all the points q ? R d : ? p ’ ? P , p ’ ? p , Dist ( q , p ) = Dist ( q , p ’).

MapReduce Programming Model: MapReduce is a popular programming framework to support data-intensive applications using shared-nothing clusters.

Voronoi Polygon: Given set of points P = { p 1 , p 2 , …, p n } where 2 < n < 8 and p i ? p j for i ? j , i, j = 1, 2, …, n , the Voronoi polygon of p i is VP( p i ) = { p | d ( p , p i ) = d ( p , p j )} for i ? j and p ? VP( p i ) where d ( p , p i ) specifies the minimum distance between p and p i in Euclidean space.

Distance between Points r and s: In n -dimensional space D , given two points r and s , | r , s | represents the distance between point r and s in space D . In this chapter, the Euclidean distance is used as the distance. AU49: Mathtype 15 where, r [ i ] (resp. s [ i ]) denotes the value of r (resp. s ) along the i th dimension in space D .

K-Means Algorithm: k -means algorithm is the well-known and commonly used clustering method. The algorithm takes the input parameter k and partitions a set X of n data points D in R d into k clusters.

K-Nearest Neighbors: Given a point r , a dataset S in space D and an integer k , the k nearest neighbors of r from S , denoted as k NN( r , s ), is a set of k point from S that ? p ? k NN( r , S ), ? s ? S - k NN( r , S ), | p , r |=| s , r |.

Complete Chapter List

Search this Book:
Reset