Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

Parallel kNN Queries for Big Data Based on Voronoi Diagram Using MapReduce

Parallel kNN Queries for Big Data Based on Voronoi Diagram Using MapReduce
View Sample PDF
Author(s): Wei Yan (Liaoning University, China)
Copyright: 2016
Pages: 22
Source title: Geospatial Research: Concepts, Methodologies, Tools, and Applications
Source Author(s)/Editor(s): Information Resources Management Association (USA)
DOI: 10.4018/978-1-4666-9845-1.ch029


View Parallel kNN Queries for Big Data Based on Voronoi Diagram Using MapReduce on the publisher's website for pricing and purchasing information.


In cloud computing environments parallel kNN queries for big data is an important issue. The k nearest neighbor queries (kNN queries), designed to find k nearest neighbors from a dataset S for every object in another dataset R, is a primitive operator widely adopted by many applications including knowledge discovery, data mining, and spatial databases. This chapter proposes a parallel method of kNN queries for big data using MapReduce programming model. Firstly, this chapter proposes an approximate algorithm that is based on mapping multi-dimensional data sets into two-dimensional data sets, and transforming kNN queries into a sequence of two-dimensional point searches. Then, in two-dimensional space this chapter proposes a partitioning method using Voronoi diagram, which incorporates the Voronoi diagram into R-tree. Furthermore, this chapter proposes an efficient algorithm for processing kNN queries based on R-tree using MapReduce programming model. Finally, this chapter presents the results of extensive experimental evaluations which indicate efficiency of the proposed approach.

Related Content

Salwa Saidi, Anis Ghattassi, Samar Zaggouri, Ahmed Ezzine. © 2021. 19 pages.
Mehmet Sevkli, Abdullah S. Karaman, Yusuf Ziya Unal, Muheeb Babajide Kotun. © 2021. 29 pages.
Soumaya Elhosni, Sami Faiz. © 2021. 13 pages.
Symphorien Monsia, Sami Faiz. © 2021. 20 pages.
Sana Rekik. © 2021. 9 pages.
Oumayma Bounouh, Houcine Essid, Imed Riadh Farah. © 2021. 14 pages.
Mustapha Mimouni, Nabil Ben Khatra, Amjed Hadj Tayeb, Sami Faiz. © 2021. 18 pages.
Body Bottom