东北大学学报:自然科学版 ›› 2020, Vol. 41 ›› Issue (7): 913-919.DOI: 10.12068/j.issn.1005-3026.2020.07.001

• 信息与控制 •    下一篇

空间多样化约束下的移动k近邻查询

许鸿斐, 谷峪, 于戈   

  1. (东北大学 计算机科学与工程学院, 辽宁 沈阳110169)
  • 收稿日期:2019-06-01 修回日期:2019-06-01 出版日期:2020-07-15 发布日期:2020-07-15
  • 通讯作者: 许鸿斐
  • 作者简介:许鸿斐(1987-),男,山西太原人,东北大学博士研究生; 谷峪(1981-),男,辽宁鞍山人,东北大学教授,博士生导师; 于戈(1962-),男,辽宁大连人,东北大学教授,博士生导师.
  • 基金资助:
    国家重点研发计划项目(2018YFB1003404); 国家自然科学基金资助项目(61872070,61602103); 中央高校基本科研业务费专项资金资助项目(N171605001).

Moving k Nearest Neighbor Query with Spatial Diversity Constraints

XU Hong-fei, GU Yu, YU Ge   

  1. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China.
  • Received:2019-06-01 Revised:2019-06-01 Online:2020-07-15 Published:2020-07-15
  • Contact: YU Ge
  • About author:-
  • Supported by:
    -

摘要: 考虑为移动中的查询对象连续返回k个距离近并且满足空间多样化约束的对象,提出了空间多样化约束下的移动k近邻(SDC-MkNN)查询.在此,满足空间多样化约束代表对象之间的相互距离大于距离阈值.为了高效处理SDC-MkNN查询问题,提出了两种基于安全区域技术的算法.算法均通过减少重新计算查询结果的次数来提高查询效率.其中一种为精确算法EA,可连续返回精确的查询结果;另一种为近似算法ρAA,可连续返回具有近似率保障的近似查询结果.采用真实数据集验证了所提出算法的有效性.

关键词: 移动k近邻查询, 空间多样化, 安全区域, 基于位置的服务, 查询算法

Abstract: A new type of queries, named moving k nearest neighbor query with spatial diversity constraints(SDC-MkNN), was proposed.When the query object is moving, this type of queries can continuously return the k nearest neighbors, and any two of the returned objects are satisfied with the spatial diversity constraints, which means the spatial distance between any two of the returned objects must be larger than the distance threshold.Based on the safe region technique, two algorithms were proposed to increase the query efficiency by reducing the frequency of the recomputation of query results.One is an exact algorithm(EA), which can continuously return exact query results, and the other is an approximate algorithm(ρAA), which can continuously return approximate query results with exact bounds.The proposed algorithms were verified by extensive experiments on a real dataset.The results confirm the superiority of the proposed algorithms over the baseline algorithm.

Key words: moving k nearest neighbor query, spatial diversity, safe region, location-based service, query processing algorithms

中图分类号: