计算机应用

作者：张瑞, 于自强, 陶明锦, 白宇杰

单位：1.烟台理工学院 信息工程学院，山东 烟台 264005；2.烟台大学 计算机与控制工程学院，山东 烟台 264005

关键词：k近邻查询,移动对象,基于位置的服务,道路网络,时空数据处理

基金：国家自然科学基金面上项目(62172351)

移动对象k近邻（kNN）查询是基于位置服务（LBS）的重要研究课题之一。不同于单查询点的kNN查询，当多个查询点同时发起查询请求时，可能出现同一个移动对象同时是多个查询点查询结果的情况。这种情况被称为查询结果冲突，查询结果冲突的多个kNN查询被称为冲突kNN查询。在实际应用中，无法将查询结果冲突的同一个移动对象同时分配给多个查询，而是需要为每个查询分别查找不同于其他查询结果的k个移动对象。因此，提出一种路网环境下的全局最优化的移动对象冲突kNN查询算法RBCS-KNN（Road-Based Conflict Sensitive K Nearest Neighbor query algorithm）。首先，在路网划分子图的基础上构建双层索引结构；其次，利用子图拓展和剪枝策略快速筛选出可能发生冲突的候选冲突查询点；再次，计算候选冲突查询点的kNN并拓展足量的候选对象，同时将所有冲突查询点动态分组；最后，利用改进的分配策略计算最优的分配方案，使所有查询点到它分配的k个移动对象的距离之和最小。在多个真实数据集上的实验结果表明，与GLAD（Grid based LAbelling with scheDuling）算法相比，RBCS-KNN的查询总距离减少了10%，验证了所提算法的正确性和良好的性能。

来源：2026年第3期

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

查看计算机应用杂志2026年第3期