分布式环境下大规模移动对象范围查询算法

doi:10.11772/j.issn.1001-9081.2021101853

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (1): 111-121.DOI: 10.11772/j.issn.1001-9081.2021101853

所属专题：数据科学与技术

分布式环境下大规模移动对象范围查询算法

马永强^1,2, 陈晓萌², 于自强^1,2

1.自然资源部城市国土资源监测与仿真重点实验室，广东深圳 518034
2.烟台大学计算机与控制工程学院，山东烟台 264005

收稿日期:2021-11-01 修回日期:2022-01-24 发布日期:2022-06-20
作者简介:马永强（1994—），男，山东枣庄人，硕士研究生，主要研究方向：时空数据处理；陈晓萌（1997—），女，山东淄博人，硕士研究生，主要研究方向：时空数据处理；于自强（1984—），男，山东青岛人，副教授，博士，CCF会员，主要研究方向：数据库、数据挖掘。 email：zqyu@ytu.edu.cn；
基金资助:
国家自然科学基金资助项目（62172351）；自然资源部城市国土资源监测与仿真重点实验室开放基金资助项目（KF?2019?04?044）。

Range query algorithm for large scale moving objects in distributed environment

MA Yongqiang^1,2, CHEN Xiaomeng², YU Ziqiang^1,2

1.Key Laboratory of Urban Land Resources Monitoring and Simulation， Ministry of Natural Resources， Shenzhen Guangdong 518034， China
2.School of Computer and Control Engineering， Yantai University， Yantai Shandong 264005， China

Received:2021-11-01 Revised:2022-01-24 Online:2022-06-20
Contact: YU Ziqiang， born in 1984， Ph. D.， associate professor. His research interests include database， data mining.
About author:MA Yongqiang， born in 1994， M. S. candidate. His research interest includes spatial-temporal data processing；CHEN Xiaomeng， born in 1997， M. S. candidate. Her research interest includes spatial-temporal data processing；
Supported by:
This work is partially supported by National Natural Science Foundation of China （62172351）， Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation， Ministry of Natural Resources （KF-2019-04-044）.

摘要/Abstract

摘要： 移动对象的连续范围查询是许多基于位置的服务的核心问题。针对该问题，提出一种面向大规模移动对象并发范围查询的分布式搜索方法。首先，设计了一种由全局网格索引（GGI）和局部弹性四叉树构成的移动对象分布式动态索引（DDI）结构。其次，提出了一种基于DDI结构的分布式查询算法（DSA），该算法首先引入了一种在移动对象和查询点的位置连续变化的情况下的查询结果增量更新策略；然后，在增量更新过程中引入一种面向多并发查询的共享计算优化策略，该策略能够根据已有计算结果对移动对象范围查询结果进行增量搜索。最后，基于德国路网模拟了3个具有不同空间分布的移动对象数据集，将DSA与NS（Naive Search）、GI（Grid Index）和分布式混合索引（DHI）进行对比。实验结果表明，与性能最好的对比算法DHI相比，DSA的初始查询时间减少了22.7%，增量查询时间减少了15.2%，性能优于对比算法。

关键词: 连续范围查询, 移动对象, 四叉树, 分布式动态索引, 基于位置的服务

Abstract: Continuous range queries over moving objects is essential to many location-based services. Aiming at this issue， a distributed search method was proposed for processing concurrent range queries over large scale moving objects. Firstly， formed by a Global Grid Index （GGI） and a local elastic quadtree， a Distributed Dynamic Index （DDI） structure was proposed. Then， a Distributed Search Algorithm （DSA） was proposed based on DDI structure. At the first time， an incremental strategy of updating the query results as objects and query points continuously changed their locations was introduced by DSA. After that， in the incremental update process， a shared computing optimization strategy for multiple concurrent queries was introduced， to incrementally search the range query results of the moving object according to the existing calculation results. Finally， three moving object datasets with different spatial distributions were simulated on the basis of the German road network， and NS （Naive Search）， GI （Grid Index） and Distributed Hybrid Index （DHI） were compared with the proposed algorithm. The results show that compared with DHI， the comparison algorithm with the best performance， DSA decreases the initial query time by 22.7%， while drops the incremental query time by 15.2%， verifying that DSA is superior to the comparison algorithms.

Key words: continuous range query, moving object, quadtree, Distributed Dynamic Index (DDI), location-based service

中图分类号:

TP392

马永强, 陈晓萌, 于自强. 分布式环境下大规模移动对象范围查询算法[J]. 计算机应用, 2023, 43(1): 111-121.

MA Yongqiang, CHEN Xiaomeng, YU Ziqiang. Range query algorithm for large scale moving objects in distributed environment[J]. Journal of Computer Applications, 2023, 43(1): 111-121.

参考文献

1 冯钧，张立霞，陆佳民，等. 路网环境下的移动对象查询技术研究综述［J］. 软件学报， 2017， 28（6）： 1606-1628. 10.13328/j.cnki.jos.005254 FENG J， ZHANG L X， LU J M， et al. Review on moving objects query techniques in road network environment［J］. Journal of Software， 2017， 28（6）： 1606-1628. 10.13328/j.cnki.jos.005254
2 汤娜，朱展豪，李晶晶，等. 时空相点移动对象数据索引PM-Tree［J］. 计算机学报， 2021， 44（3）： 579-593. 10.11897/SP.J.1016.2021.00579 TANG N， ZHU Z H， LI J J， et al. Temporal-spatial phase point moving object data indexing： PM-tree［J］. Chinese Journal of Computers， 2021， 44（3）： 579-593. 10.11897/SP.J.1016.2021.00579
3 YU Z Q， XHAFA F， CHEN Y H， et al. A distributed hybrid index for processing continuous range queries over moving objects［J］. Soft Computing， 2019， 23（9）： 3191-3205. 10.1007/s00500-017-2973-0
4 KALASHNIKOV D， PRABHAKAR S， HAMBRUSCH S， et al. Efficient evaluation of continuous range queries on moving objects［C］// Proceedings of the 2002 International Conference on Database and Expert Systems Applications， LNCS 2453. Berlin： Springer， 2002： 731-740.
5 DONG T Y， YUAN L L， CHENG Q， et al. Direction-aware KNN queries for moving objects in a road network［J］. World Wide Web， 2019， 22（4）： 1765-1797. 10.1007/s11280-019-00657-1
6 董天阳，尚跃辉，程强. 方向感知的路网移动对象范围查询算法［J］. 计算机科学， 2018， 45（11）： 210-219. 10.11896/j.issn.1002-137X.2018.11.033 DONG T Y， SHANG Y H， CHENG Q. Direction-aware moving object range query algorithm in road network［J］. Computer Science， 2018， 45（11）： 210-219. 10.11896/j.issn.1002-137X.2018.11.033
7 薛忠斌，周烜，王珊. 双流模式下高吞吐量移动对象范围查询算法［J］. 软件学报， 2015， 26（10）：2631-2643. 10.13328/j.cnki.jos.004809 XUE Z B， ZHOU X， WANG S. Throughput oriented range query algorithm for moving objects in dual stream mode［J］. Journal of Software， 2015， 26（10）： 2631-2643. 10.13328/j.cnki.jos.004809
8 YU X， PU K Q， KOUDAS N. Monitoring k-nearest neighbor queries over moving objects［C］// Proceedings of the 21st International Conference on Data Engineering. Piscataway： IEEE， 2005： 631-642.
9 OUYANG D， WEN D， QIN L， et al. Progressive top-k nearest neighbors search in large road networks［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020： 1781-1795. 10.1145/3318464.3389746
10 FU X Y， MIAO X Y， XU J L， et al. Continuous range-based skyline queries in road networks［J］. World Wide Web， 2017， 20（6）： 1443-1467. 10.1007/s11280-017-0444-2
11 AL-KHALIDI H， TANIAR D， BETTS J， et al. On finding safe regions for moving range queries［J］. Mathematical and Computer Modelling， 2013， 58（5/6）： 1449-1458. 10.1007/s00607-012-0219-7
12 AL-KHALIDI H， TANIAR D， SAFAR M. Approximate algorithms for static and continuous range queries in mobile navigation［J］. Computing， 2013， 95（10/11）： 949-976. 10.1007/s00607-012-0219-7
13 CAI Y， HUA K A， CAO G H. Processing range-monitoring queries on heterogeneous mobile objects［C］// Proceedings of the 2004 IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2004： 27-38. 10.1109/mdm.2004.1324416
14 ZHANG D X， YANG D Y， WANG Y， et al. Distributed shortest path query processing on dynamic road networks［J］. The VLDB Journal， 2017， 26（3）： 399-419. 10.1007/s00778-017-0457-6
15 HU H B， XU J L， LEE D L. A generic framework for monitoring continuous spatial queries over moving objects［C］// Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2005： 479-490. 10.1145/1066157.1066212
16 ZHOU Y T， TANG X L， HU P. Comparative analysis of indoor positioning technology［J］. Engineering Technology Research， 2019， 1（3）： 162-164.
17 WANG Z J， YAO B， CHENG R， et al. SMe： explicit & implicit constrained-space probabilistic threshold range queries for moving objects［J］. GeoInformatica， 2016， 20（1）： 19-58. 10.1007/s10707-015-0230-1
18 SHAO Z， CHEEMA M A， TANIAR D， et al. VIP-Tree： an effective index for indoor spatial queries［J］. Proceedings of the VLDB Endowment， 2016， 10（4）： 325-336. 10.14778/3025111.3025115
19 SILVESTRI C， LETTICH F， ORLANDO S， et al. GPU-based computing of repeated range queries over moving objects［C］// Proceedings of the 22nd Euromicro International Conference on Parallel， Distributed， and Network-Based Processing. Piscataway： IEEE， 2014： 640-647. 10.1109/pdp.2014.27
20 冯钧，李顶圣，陆佳民，等. 基于HBase的路网移动对象时空索引方法［J］. 计算机应用， 2018， 38（6）： 1575-1583， 1590. 10.11772/j.issn.1001-9081.2017122977 FENG J， LI D S， LU J M， et al. Spatio-temporal index method for moving objects in road network based on HBase［J］. Journal of Computer Applications， 2018， 38（6）： 1575-1583， 1590. 10.11772/j.issn.1001-9081.2017122977
21 徐江峰，谭玉龙. 基于HBase的多维索引查询机制的优化［J］. 计算机应用， 2020， 40（2）： 571-577. XU J F， TAN Y L. Optimization of multidimensional index query mechanism based on HBase［J］. Journal of Computer Applications， 2020， 40（2）： 571-577.

[1]	陈国祥, 于自强, 赵浩宇. 面向动态路网的移动对象分布式k近邻查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3403-3410.
[2]	胡立华, 李小平, 胡建华, 张素兰. 基于四叉树先验辅助的多视图立体方法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3556-3564.
[3]	包玄, 陈红梅, 肖清. 融入时间的兴趣点协同推荐算法[J]. 计算机应用, 2021, 41(8): 2406-2411.
[4]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[5]	徐江峰, 谭玉龙. 基于HBase的多维索引查询机制的优化[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 571-577.
[6]	付宇, 王红. 位置隐私保护的虚拟轨迹填充算法[J]. 计算机应用, 2019, 39(8): 2318-2325.
[7]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[8]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[9]	李琰, 刘嘉勇. 基于作者主题模型和辐射模型的用户位置预测模型[J]. 计算机应用, 2018, 38(4): 939-944.
[10]	赵大鹏, 宋光旋, 靳远远, 王晓玲. 基于查询概率的位置隐私保护方法[J]. 计算机应用, 2017, 37(2): 347-351.
[11]	吕绍仟, 孟凡荣, 袁冠. 基于轨迹结构的移动对象热点区域发现[J]. 计算机应用, 2017, 37(1): 54-59.
[12]	宋路杰, 孟凡荣, 袁冠. 基于Markov模型与轨迹相似度的移动对象位置预测算法[J]. 计算机应用, 2016, 36(1): 39-43.
[13]	张峻, 董兰芳, 余家奎. 高效率视频编码快速帧内预测算法[J]. 计算机应用, 2015, 35(8): 2327-2331.
[14]	李振举, 李学军, 谢剑薇, 李雁南. 基于HBase的海量地形数据存储[J]. 计算机应用, 2015, 35(7): 1849-1853.
[15]	王文博, 殷宏, 解文彬, 王家腾. 基于硬件细分的层次细节地形渲染算法[J]. 计算机应用, 2015, 35(6): 1716-1719.

分布式环境下大规模移动对象范围查询算法

Range query algorithm for large scale moving objects in distributed environment

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics