加权路网空间中动态聚集最近邻居查询算法  

Dynamic aggregate nearest neighbor query algorithm in weighted road network space

作　　者：陈方疏 张为 胡小明[1] 张宇飞 孟宪凯 石林祥[1] CHEN Fangshu;ZHANG Wei;HU Xiaoming;ZHANG Yufei;MENG Xiankai;SHI Linxiang(School of Computer and Information Engineering,Shanghai Polytechnic University,Shanghai 201209,China)

机构地区：[1]上海第二工业大学计算机与信息工程学院,上海201209

出　　处：《计算机应用》2023年第7期2026-2033,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62002216);上海市青年科技英才扬帆计划项目(20YF1414400);上海第二工业大学青年基金资助项目(EGD22QD03);上海第二工业大学电子信息类专业硕士协同创新平台建设项目(A10GY21F015)。

摘　　要：聚集最近邻居(ANN)查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义,能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足:缺少针对大规模动态路网数据的高效索引结构,在数据点位置实时移动以及路网权重动态更新的场景下算法的查询效率较低。针对上述不足,提出动态场景下的ANN查询算法。首先利用G-tree作为路网索引,提出将四叉树和k-d树等空间索引结构与增量欧氏空间限制(IER)算法结合起来的剪枝方法,以完成静态空间下的ANN查询;随后针对动态场景下数据点位置频繁更新的问题,加入时间窗口及安全区域更新策略,以减少算法的重复计算次数,实验结果表明效率能提高8%~85%;最后针对路网权重变化的ANN查询问题,提出两个基于校正的连续查询方法,在历史查询结果的基础上,根据权重变化的增量来得到当前的查询结果,在某些场景中能够有效降低50%左右的误差。理论研究和实验结果表明,所提算法能够高效并且较为准确地解决动态场景下的ANN查询问题。As a classical problem in spatial databases,Aggregate Nearest Neighbor(ANN)query is of great importance in the optimization of network link structures,the location selection of logistics distribution points and the car-sharing services,and can effectively contribute to the development of fields such as logistics,mobile Internet industry and operations research.The existing research has some shortcomings:lack of efficient index structure for large-scale dynamic road network data,low query efficiency of the algorithms when the data point locations move in real time and network weights update dynamically.To address these problems,an ANN query algorithm in dynamic scenarios was proposed.Firstly,with adopting G-tree as the road network index,a pruning algorithm combining spatial index structures such as quadtrees and k-d trees with the Incremental Euclidean Restriction(IER)algorithm was proposed to solve ANN queries in statistic space.Then,aiming at the issue of frequent updates of data point locations in dynamic scenarios,the time window and safe zone update strategy were added to reduce the iteration times of the algorithm,experimental results showed that the efficiency could be improved by 8% to 85%.Finally,for ANN query problems with road network weight changed,based on historical query results,two correction based continuous query algorithms were proposed to obtain the current query results according to the increment of weight changes.In certain scenarios,these algorithms can reduce errors by approximately 50%.The theoretical research and experimental results show that the proposed algorithms can solve the ANN query problems in dynamic scenarios efficiently and more accurately.

关 键 词：聚集最近邻居查询 路网 加权空间 动态查询 空间索引 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]