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

Range query algorithm for large scale moving objects in distributed environment

作　　者：马永强[1,2] 陈晓萌 于自强 MA Yongqiang;CHEN Xiaomeng;YU Ziqiang(Key Laboratory of Urban Land Resources Monitoring and Simulation,Ministry of Natural Resources,Shenzhen Guangdong 518034,China;School of Computer and Control Engineering,Yantai University,Yantai Shandong 264005,China)

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

出　　处：《计算机应用》2023年第1期111-121,共11页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62172351);自然资源部城市国土资源监测与仿真重点实验室开放基金资助项目(KF-2019-04-044)。

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

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

分 类 号：TP392[自动化与计算机技术—计算机应用技术]