Inverted Voronoi-Based kNN Query Processing with MapReduce

摘要

In mobile cloud computing environments distributed k Nearest Neighbor (kNN) query is an important issue. We consider the problem of processing kNN query over large data sets where the index is jointly maintained by a set of machines in a computing cluster. The kNN query is a primitive operator that is widely used in many fields ranging from knowledge discovery, data mining and spatial databases etc. A scalable and distributed spatial data index plays an important role in conducting kNN query effectively. We can use different ways to conduct distributed indexes and kNN query processing by using MapReduce, i.e. R-tree and Grid-based index, etc. Nevertheless, R-tree is not compatible with parallelization, and Grid is a many-to-many index, which could potentially lead to content redundancy. In the paper, a distributed method of kNN queries applying MapReduce program model will be introduced. In the very beginning, I propose distributed methods which set up a novel distributed spatial data index: Inverted Voronoi Index that combines both inverted index and Voronoi diagram. Next, I propose a kNN queries processing algorithm, it is very efficient because it is based on Voronoi and uses MapReduce. Last but not least, I present the outcomes of extensive experiment that are gained by both real and simulated data sets which indicate efficiency and scalability of the proposed approach.