计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (2): 206-212.DOI: 10.3778/j.issn.1002-8331.1708-0228

• 工程与应用 • 上一篇    下一篇

基于空间近邻查询的移动医疗呼叫算法

季长清1,2,肖  鹏3,刘  畅4,汪祖民2,西  方2,邵寅博1,李泽宇2   

  1. 1.大连大学 物理科学与技术学院,辽宁 大连 116622
    2.大连大学 信息工程学院,辽宁 大连 116622
    3.大连工业大学 信息科学与工程学院,辽宁 大连 116000
    4.大连大学 环境与化学工程学院,辽宁 大连 116622
  • 出版日期:2019-01-15 发布日期:2019-01-15

Mobile Medical Call Algorithms Based on Spatial kNN Query

JI Changqing1,2, XIAO Peng3, LIU Chang4, WANG Zumin2, XI Fang2, SHAO Yinbo1, LI Zeyu2   

  1. 1.School of Physical Science and Technology, Dalian University, Dalian, Liaoning 116622, China
    2.School of Information Engineering, Dalian University, Dalian, Liaoning 116622, China
    3.School of Information Science and Engineering, Dalian Polytechnic University, Dalian, Liaoning 116000, China
    4.School of Environmental and Chemical Engineering, Dalian University, Dalian, Liaoning 116622, China
  • Online:2019-01-15 Published:2019-01-15

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

关键词: [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