面向移动对象连续k近邻查询的双层索引结构
作者:
作者简介:

韩士元(1985-),男,博士,副教授,CCF专业会员,主要研究领域为智能交通系统复杂数据分析及应用;何清(1996-),男,硕士,主要研究领域为时空大数据;于自强(1984-),男,博士,副教授,CCF专业会员,主要研究领域为海量数据管理与分析,流数据分布式计算,视频数据结构化查询;童向荣(1975-),男,博士,教授,CCF高级会员,主要研究领域为多Agent系统,分布式人工智能,数据挖掘技术;郑渤龙(1989-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为时空大数据管理与分析,高维数据管理,城市计算

通讯作者:

于自强,zqyu@ytu.edu.cn

中图分类号:

TP311

基金项目:

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


Double Layer Index for Continuous k-nearest Neighbor Queries on Moving Objects
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [29]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    移动对象连续k近邻(CKNN)查询是指给定一个连续移动的对象集合,对于任意一个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 needs 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 study 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 the proposed proposal.

    参考文献
    [1] Zheng YL. A fast index method for moving objects on full temporal query. In: Proc. of the 3rd Int’l Conf. on Computer Research and Development. Shanghai: IEEE, 2011. 205–208.
    [2] Zhong RC, Li GL, Tan KL, Zhou LZ, Gong ZG. G-Tree: An efficient and scalable index for spatial search on road networks. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(8): 2175–2189. [doi: 10.1109/TKDE.2015.2399306]
    [3] Shen BL, Zhao Y, Li GL, Zheng WM, Qin Y, Yuan B, Rao YM. V-Tree: Efficient kNN search on moving objects with road-network constraints. In: Proc. of the 33rd Int’l Conf. on Data Engineering. San Diego: IEEE, 2017. 609–620.
    [4] Zheng BL, Zhao X, Weng LG, Hung NQV, Liu H, Jensen CS. PM-LSH: A fast and accurate LSH framework for high-dimensional approximate NN Search. Proceedings of the VLDB Endowment, 2020, 13(5): 643–655. [doi: 10.14778/3377369.3377374]
    [5] Nutanong S, Zhang R, Tanin E, Kulik L. The V*-Diagram: A query-dependent approach to moving kNN queries. Proceedings of the VLDB Endowment, 2008, 1(1): 1095–1106.
    [6] Hu L, Ku WS, Bakiras S, Shahabi C. Spatial query integrity with voronoi neighbors. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(4): 863–876. [doi: 10.1109/TKDE.2011.267]
    [7] Zhu HJ, Yang XC, Wang B, Lee WC, Yin J, Xu JL. Processing continuous k nearest neighbor queries in obstructed space with voronoi diagrams. ACM Transactions on Spatial Algorithms and Systems, 2021, 7(2): 8. [doi: 10.1145/3425955]
    [8] Ni WW, Li LQ, Liu JQ. Voronoi-R*-based privacy-preserving k nearest neighbor query over road networks. Ruan Jian Xue Bao/Journal of Software, 2019, 30(12): 3782–3797 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5583.htm 倪巍伟, 李灵奇, 刘家强. 基于Voronoi-R*的隐私保护路网k近邻查询方法. 软件学报, 2019, 30(12): 3782–3797. http://www.jos.org.cn/1000-9825/5583.htm
    [9] Šidlauskas D, Šaltenis S, Jensen CS. Parallel main-memory indexing for moving-object query and update workloads. In: Proc. of the 2012 ACM SIGMOD Int’l Conf. on Management of Data. Arizona: ACM, 2012. 37–48.
    [10] Kumar S, Madria S, Linderman M. M-Grid: A distributed framework for multidimensional indexing and querying of location based data. Distributed and Parallel Databases, 2017, 35(1): 55–81. [doi: 10.1007/s10619-017-7194-0]
    [11] Xu XF, Xiong L, Sunderam V. D-Grid: An in-memory dual space grid index for moving object databases. In: Proc. of the 17th IEEE Int’l Conf. on Mobile Data Management. Porto: IEEE, 2016. 252–261.
    [12] Yang KT, Chiu G M. Monitoring continuous all k-nearest neighbor query in mobile network environments. Pervasive and Mobile Computing, 2017, 39: 231–248. [doi: 10.1016/j.pmcj.2016.07.002]
    [13] Yi X, Paule R, Bertino E, Varadharajan V. Practical approximate k nearest neighbor queries with location and query privacy. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(6): 1546–1559. [doi: 10.1109/TKDE.2016.2520473]
    [14] Li K, Malik J. Fast k-nearest neighbour search via dynamic continuous indexing. In: Proc. of the 33rd Int’l Conf. on Machine Learning. New York: JMLR, 2016. 671–679.
    [15] Yu XH, Pu KQ, Koudas N. Monitoring k-nearest neighbor queries over moving objects. In: Proc. of the 21st Int’l Conf. on Data Engineering. Tokyo: IEEE, 2005. 631–642.
    [16] Mouratidis K, Papadias D, Hadjieleftheriou M. Conceptual Partitioning: An efficient method for continuous nearest neighbor monitoring. In: Proc. of the 2005 ACM SIGMOD Int’l Conf. on Management of Data. Maryland: ACM, 2005. 634–645.
    [17] Hua H, Xie HR, Tanin E. Is euclidean distance really that bad with road networks? In: Proc. of the 11th ACM SIGSPATIAL Int’l Workshop on Computational Transportation Science. Seattle: ACM, 2018. 11–20.
    [18] Nutanong S, Ali ME, Tanin E, Mouratidis K. Dynamic nearest neighbor queries in euclidean space. In: Shekhar S, Xiong H, Zhou X, eds. Encyclopedia of GIS. Cham: Springer, 2017. 496–501.
    [19] Miao X, Guo X, Wang H, Wang ZS, Ye XD. Continuous nearest neighbor query with the direction constraint. In: Proc. of the 17th Int’l Symp. on Web and Wireless Geographical Information Systems. Kyoto: Springer, 2019. 85–101.
    [20] Lee JM. Fast k-nearest neighbor searching in static objects. Wireless Personal Communications, 2017, 93(1): 147–160. [doi: 10.1007/s11277-016-3524-1]
    [21] Liu J. Research on multi-source nearest neighbor query method in road network environment [Ph.D. Thesis]. Qinhuangdao: Yanshan University, 2019. 3 (in Chinese with English abstract). 刘佳. 路网环境下的多源最近邻查询方法研究 [博士学位论文]. 秦皇岛: 燕山大学, 2019. 3.
    [22] Cheema MA, Zhang WJ, Lin XM, Zhang Y, Li XF. Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. The VLDB Journal, 2012, 21(1): 69–95. [doi: 10.1007/s00778-011-0235-9]
    [23] Li CW, Gu Y, Qi JZ, Yu G, Zhang R, Yi W. Processing moving kNN queries using influential neighbor sets. Proceedings of the VLDB Endowment, 2014, 8(2): 113–124. [doi: 10.14778/2735471.2735473]
    [24] Zheng BL, Zheng K, Jensen CS, Hung NQV, Su H, Li GH, Zhou XF. Answering why-not group spatial keyword queries. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(1): 26–39. [doi: 10.1109/TKDE.2018.2879819]
    [25] Wang WC, Wong RCW, Xie M. Interactive search for one of the top-k. In: Proc. of the 2021 Int’l Conf. on Management of Data. Virtual Event: ACM, 2021. 1920–1932.
    [26] Li MQ, He D, Zhou XF. Efficient kNN search with occupation in large-scale on-demand ride-hailing. In: Proc. of the 31st Australasian Database Conf. Melbourne: Springer, 2020. 29–41.
    [27] Lee K, Ganti RK, Srivatsa M, Liu L. Efficient spatial query processing for big data. In: Proc. of the 22nd ACM SIGSPATIAL Int’l Conf. on Advances in Geographic Information Systems. Texas: ACM, 2014. 469–472.
    [28] Bao JL, Wang B, Yang XC, Zhu HJ. Nearest neighbor query in road networks. Ruan Jian Xue Bao/Journal of Software, 2018, 29(3): 642–662 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5442.htm 鲍金玲, 王斌, 杨晓春, 朱怀杰. 路网环境下的最近邻查询技术. 软件学报, 2018, 29(3): 642–662. http://www.jos.org.cn/1000-9825/5442.htm
    [29] Feng J, Zhang LX, Lu JM, Wang C. Review on moving objects query techniques in road network environment. Ruan Jian Xue Bao/Journal of Software, 2017, 28(6): 1606–1628 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5254.htm 冯钧, 张立霞, 陆佳民, 王冲. 路网环境下的移动对象查询技术研究综述. 软件学报, 2017, 28(6): 1606–1628. http://www.jos.org.cn/1000-9825/5254.htm
    相似文献
    引证文献
引用本文

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

复制
相关视频

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

京公网安备 11040202500063号