Wei Yan (Liaoning University, China)

Copyright: © 2019
|Pages: 22

DOI: 10.4018/978-1-5225-8446-9.ch011

Chapter Preview

TopThe *k* nearest neighbor query (*k*NN 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 (*k*NN) is a special type of query that is *k* nearest neighbors from points in *S* for each query point *r* in dataset *R*. The *k*NN query typically serves as a primitive operation and is widely used in spatial databases. The basic idea of implementing *k*NN 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 *k*NN queries and reduce the computational complexity of the *k*NN 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 *k*NN 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 *k*NN queries over massive spatial datasets. This chapter proposes a method of parallel *k*NN 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 *k*NN 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 *k*NN 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 *k*NN-join algorithm, called the Gorder *k*NN 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 *k*NN 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.

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 |.

Search this Book:

Reset

Copyright © 1988-2019, IGI Global - All Rights Reserved