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 ’).
Published in Chapter:
Voronoi-Based kNN Queries Using K-Means Clustering in MapReduce
Wei Yan (Liaoning University, China)
Copyright: © 2019
|Pages: 22
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.