面向移动对象连续K近邻查询的双层索引结构
作者:
作者单位:

作者简介:

通讯作者:

于自强,E-mail:zqyu@ytu.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(62172351, 62072392, 61903156, 61873324); 山东省自然科学基金重点项目(ZR2020KF006)


Double Layer Index for Continuous K-Nearest Neighbor Queries on Moving Objects
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    移动对象连续k近邻查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询qk近邻并在查询有效时间内对查询结果进行实时更新。现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题。已有研究工作解决连续k近邻查询问题时,大多需要通过多次迭代确定一个包含k近邻的查询范围,而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量,整个迭代过程的计算代价占查询代价的很大部分。为此,提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构(Grid GMM Index, GGI),并设计了移动对象连续k近邻增量查询算法(Incremental Search for Continuous K Nearest Neighbors, IS-CKNN)。GGI索引结构的底层采用网格索引对海量移动对象进行维护,上层构建混合高斯模型模拟移动对象在二维空间中的分布。对于给定的k近邻查询q,IS-CKNN算法能够基于混合高斯模型直接确定一个包含qk近邻的查询区域,减少了已有算法求解该区域的多次迭代过程;当移动对象和查询q位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量。最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能。

    Abstract:

    For a given set of moving objects, Continuous k Nearest Neighbor (CkNN) query q over moving objects is to quickly identify and monitor the k nearest objects as objects and the query point evolve. In real life, many location-based applications in transportation, social network, e-commerce, and other fields involve the basic problem of processing CkNN queries over moving objects. Most of existing work processing CkNN queries usually need to determine a query range containing k nearest neighbors through multiple iterations, while each iteration has to identify the number of objects in the current query range, and which dominates the query cost. In order to address this issue, this work proposes a dual index called GGI that consists of a grid index and a Gaussian mixture function to simulate the varying distribution of objects. The bottom layer of GGI employs a grid index to maintain moving objects, and the upper layer constructs Gaussian mixture model to simulate the distribution of moving objects in two-dimensional space. Based on GGI, an incremental search algorithm called IS-CKNN to process CkNN queries. This algorithm directly determines a query region that at least contains k neighbors of q based on Gaussian mixture model, which greatly reduces the number of iterations. When the objects and query point evolve, an efficient incremental query strategy is further proposed, which can maximize the use of existing query results and reduce the calculation of the current query. Finally, extensive experiments are carried out on one real dataset and two synthetic datasets to confirm the superiority of our proposal.

    参考文献
    相似文献
    引证文献
引用本文

韩士元,何清,于自强,童向荣,郑渤龙.面向移动对象连续K近邻查询的双层索引结构.软件学报,,():0

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-04-20
  • 最后修改日期:2021-07-17
  • 录用日期:
  • 在线发布日期: 2022-01-28
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号