计算机应用

作者：马永强, 陈晓萌, 于自强

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

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

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

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

来源：2023年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2023年第1期