Title :
Efficient Multi-dimensional Spatial RkNN Query Processing with MapReduce
Author :
Changqing Ji ; Hongbin Hu ; Yujie Xu ; Yuanyuan Li ; Wenyu Qu
Author_Institution :
Coll. of Inf. Sci. & Technol., Dalian Maritime Univ., Dalian, China
Abstract :
Reverse k Nearest Neighbor (RkNN) queries are of particular interest in a wide range of data mining applications such as decision support systems, profile based marketing and spatial database etc. With the increasing volume of spatial data, it is difficult to perform RkNN queries efficiently because of the limited computational capability and storage resources. In this paper, we investigate how to perform distributed RkNN queries using MapReduce. Firstly, we investigate the Basic-MRRkNN query method based on the inverted grid index over large scale spatial datasets. Secondly, we propose an optimization method: Lazy-MRRkNN query algorithm that prunes the search space when all data points are discovered. To the best of our knowledge, it is the first time that we propose exact RkNN processing algorithms using MapReduce on multi-dimensional datasets. Extensive experiments using both real and synthetic datasets demonstrated that our proposed methods are efficient and scalable.
Keywords :
data mining; distributed databases; query processing; visual databases; Basic-MRRkNN query method; Lazy-MRRkNN query algorithm; MapReduce; data mining applications; distributed RkNN queries; exact RkNN processing algorithms; inverted grid index; large scale spatial datasets; multidimensional datasets; multidimensional spatial RkNN query processing; optimization method; reverse k nearest neighbor queries; search space; Algorithm design and analysis; Approximation algorithms; Filtering algorithms; Indexes; Query processing; Spatial databases; Time factors; MapReduce; Reverse Nearest Neighbors; Spatial Databases;
Conference_Titel :
ChinaGrid Annual Conference (ChinaGrid), 2013 8th
Conference_Location :
Changchun
Print_ISBN :
978-0-7695-5058-9
DOI :
10.1109/ChinaGrid.2013.17