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

摘要： 随着大数据时代的到来，传统的计算机因为单机资源有限、运行速度慢、分布式处理支持差，已满足不了现行的医疗体系中的大数据处理需求，基于时空数据的移动医疗呼叫系统方法可以很好地解决这些问题。在移动云计算环境下研究[k]最近邻查询算法是当前一个热点问题，支持可扩展和分布式的空间数据索引对于kNN查询的效率影响很大，目前已有的查询算法不适合并行化或者会导致内容冗余。将MapReduce分布式处理技术与空间kNN查询方法相结合，设计可以快速检索到满足用户查询需求的医生位置信息的移动医疗呼叫算法。提出并构建了一个新的分布式空间数据索引方法：倒排Voronoi图索引，它将倒排索引和Voronoi图索引进行结合；提出了一种基于MapReduce的利用Voronoi图来处理kNN查询的高效算法，其在分布式环境下可以有效提高查询效率；用真实的和仿真的数据集来进行大量实验评估，实验结果表明所提出的方法具有良好的高效性和可扩展性。

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