面向动态路网的移动对象分布式k近邻查询算法

来源：计算机应用杂志2024年第11期北京时间：

作者：陈国祥, 于自强, 赵浩宇

单位：烟台大学 计算机与控制工程学院，山东 烟台 264005

摘要：动态路网k近邻（kNN）查询是许多基于位置的服务（LBS）中的一个重要问题。针对该问题，提出一种面向动态路网的移动对象分布式kNN查询算法DkNN（Distributed kNN）。首先，将整个路网划分为部署于集群中不同节点中的多个子图；其次，通过并行地搜索查询范围所涉及的子图得到精确的kNN结果；最后，优化查询的搜索过程，引入查询范围剪枝策略和查询终止策略。在4个道路网络数据集上与3种基线算法进行了充分对比和验证。实验结果显示，与TEN*-Index （Tree dEcomposition based kNN* Index）算法相比，DkNN算法的查询时间减少了56.8%，路网更新时间降低了3个数量级。DkNN算法可以快速响应动态路网中的kNN查询请求，且在处理路网更新时具有较低的更新成本。

关键词：动态道路网络,k近邻查询,分布式环境,基于位置的服务,时空数据处理

基金资助：国家自然科学基金资助项目(62172351)