关键词: [k]最近邻, Voronoi图, MapReduce, 空间数据索引

Abstract: With the arrival of the “Big Data age”, the traditional computer runs slowly and does not support distribution, it can’t meet the current needs of big data processing in the medical system, and mobile medical call system based on spatial-temporal data can solve these problems. In the mobile cloud computing environment, the [k] nearest neighbor query algorithm is an important issue. Scalable and distributed spatial data indexes are also important for kNN queries. But the existing method is not suitable for parallelization or it will lead to content redundancy. In this paper, it proposes a distributed method of kNN queries using MapReduce programming model and designs a mobile medical calling algorithm which the information of doctors can be quickly queried to satisfy the users’ demand for query. Firstly, it presents and constructs a distributed spatial index：inverted Voronoi index, which combines the inverted index with the Voronoi index. Secondly, it proposes an efficient algorithm for kNN queries using MapReduce. Finally, it presents the results of extensive experimental evaluations which indicate efficiency and scalability of the proposed approach using real and synthetic data sets.

Key words: [k] nearest neighbors, Voronoi, MapReduce, spatial data index