计算机应用

作者：陈方疏, 张为, 胡小明, 张宇飞, 孟宪凯, 石林祥

单位：上海第二工业大学 计算机与信息工程学院，上海 201209

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

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

聚集最近邻居（ANN）查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义，能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足：缺少针对大规模动态路网数据的高效索引结构，在数据点位置实时移动以及路网权重动态更新的场景下算法的查询效率较低。针对上述不足，提出动态场景下的ANN查询算法。首先利用G-tree作为路网索引，提出将四叉树和k-d树等空间索引结构与增量欧氏空间限制（IER）算法结合起来的剪枝方法，以完成静态空间下的ANN查询；随后针对动态场景下数据点位置频繁更新的问题，加入时间窗口及安全区域更新策略，以减少算法的重复计算次数，实验结果表明效率能提高8%~85%；最后针对路网权重变化的ANN查询问题，提出两个基于校正的连续查询方法，在历史查询结果的基础上，根据权重变化的增量来得到当前的查询结果，在某些场景中能够有效降低50%左右的误差。理论研究和实验结果表明，所提算法能够高效并且较为准确地解决动态场景下的ANN查询问题。

来源：2023年第7期

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

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