路网环境下移动对象冲突k近邻查询

doi:10.11772/j.issn.1001-9081.2025040442

《计算机应用》唯一官方网站 ›› 2026, Vol. 46 ›› Issue (3): 781-789.DOI: 10.11772/j.issn.1001-9081.2025040442

路网环境下移动对象冲突k近邻查询

张瑞¹^,², 于自强¹^,²(), 陶明锦², 白宇杰²

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

收稿日期:2025-04-22 修回日期:2025-07-10 接受日期:2025-07-14 发布日期:2025-07-24 出版日期:2026-03-10
通讯作者: 于自强
作者简介:张瑞（2000—），女，山东菏泽人，硕士研究生，主要研究方向：时空数据处理
陶明锦（2001—），男，江苏常州人，硕士研究生，主要研究方向：时空数据处理
白宇杰（2001—），男，山西晋城人，硕士研究生，主要研究方向：数据库。
基金资助:
国家自然科学基金面上项目(62172351)

Conflict-aware k-nearest neighbor query over moving objects in road networks

Rui ZHANG¹^,², Ziqiang YU¹^,²(), Mingjin TAO², Yujie BAI²

^1.School of Information Engineering，Yantai Institute of Technology，Yantai Shandong 264005，China
^2.School of Computer and Control Engineering，Yantai University，Yantai Shandong 264005，China

Received:2025-04-22 Revised:2025-07-10 Accepted:2025-07-14 Online:2025-07-24 Published:2026-03-10
Contact: Ziqiang YU
About author:ZHANG Rui， born in 2000， M. S. candidate. Her research interests include spatial-temporal data processing.
TAO Mingjin， born in 2001， M. S. candidate. His research interests include spatial-temporal data processing.
BAI Yujie， born in 2001， M. S. candidate. His research interests include database.
Supported by:
General Program of National Natural Science Foundation of China(62172351)

摘要/Abstract

摘要：

移动对象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%，验证了所提算法的正确性和良好的性能。

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

Abstract:

The k-nearest neighbor （kNN） query over moving objects is one of the important research topics in Location-Based Service （LBS）. Unlike kNN queries with a single query point， when a large number of query points issue query requests simultaneously， the same moving object may appear in the query results of multiple query points. This situation is called query result conflict， and multiple kNN queries involved in such conflicts are called conflict-aware kNN queries. In practical applications， the same moving object involved in query result conflicts cannot be assigned to multiple queries simultaneously. Instead， each query must retrieve k moving objects that differ from the results of other queries. Therefore， a globally optimized algorithm for conflict-aware kNN queries named RBCS-KNN （Road-Based Conflict Sensitive K Nearest Neighbor query algorithm） was proposed for road networks. Firstly， a two-layer index structure was built on the basis of the road network subgraphs after dividing. Secondly， by subgraph expansion and pruning strategies， the candidate conflicting query points were screened rapidly. Thirdly， kNN for the candidate query points were computed， and a sufficient number of candidate objects were expanded， while all conflicting query points were grouped dynamically. Finally， an optimal assignment solution was determined via an improved assignment strategy by which the sum of the distance from every query point to its k moving objects was minimized. Experimental results on multiple real-world datasets show that RBCS-KNN reduces the total query distance by 10% compared to the GLAD （Grid based LAbelling with scheDuling） algorithm， demonstrating its correctness and good performance.

Key words: k-Nearest Neighbor (kNN) query, moving object, Location-Based Service (LBS), road network, spatial-temporal data processing

中图分类号:

TP392

张瑞, 于自强, 陶明锦, 白宇杰. 路网环境下移动对象冲突k近邻查询[J]. 计算机应用, 2026, 46(3): 781-789.

Rui ZHANG, Ziqiang YU, Mingjin TAO, Yujie BAI. Conflict-aware k-nearest neighbor query over moving objects in road networks[J]. Journal of Computer Applications, 2026, 46(3): 781-789.

图/表 13

图1 冲突示意图

Fig. 1 Schematic diagram of conflict

图2 双层图索引结构的示例

Fig. 2 Example of two-layer graph index structure

图3 计算初始查询区域的示例

Fig. 3 Example of computing initial query region

图4 二部图改进的示例

Fig. 4 B Example of bipartite graph improvement

表1 实验中使用的道路网络数据集

Tab. 1 Road network datasets used in experiments

数据集	顶点数	边数	平均路段权重
NY	264 346	733 846	1 794
COL	435 666	1 057 066	2 184
FLA	1 070 376	2 712 798	2 588
CAL	1 890 815	4 657 742	3 318

表2 实验中使用的参数

Tab. 2 Parameters used in experiments

参数	解释	数值范围
$β$	查询数	50，100，150，200
$α$	移动对象数	10 000，15 000，20 000，25 000
$k$	指定的k值	5，10，15，20
$m$	子图顶点数	23，28，33，38，43

表2 实验中使用的参数

Tab. 2 Parameters used in experiments

参数	解释	数值范围
$β$	查询数	50，100，150，200
$α$	移动对象数	10 000，15 000，20 000，25 000
$k$	指定的k值	5，10，15，20
$m$	子图顶点数	23，28，33，38，43

图5 索引构建成本的对比

Fig. 5 Index construction cost comparison

图6 k对查询时间的影响

Fig. 6 Impact of k on query time

图7 子图大小对查询时间的影响

Fig. 7 Impact of subgraph size on query time

图8 α和β对查询时间的影响

Fig. 8 Impact of α and β on query time

图9 优化剪枝前后的效率对比

Fig. 9 Performance comparison before and after pruning

表3 RBCS-KNN和GLAD中的冲突情况

Tab. 3 Conflict situations in RBCS-KNN and GLAD

算法	k	冲突查询点数	冲突查询组数	冲突的移动对象数
RBCS-KNN	5	8	4	24
	10	20	8	110
	15	33	14	228
	20	51	22	388
GLAD	5	2	1	6
	10	6	3	28
	15	9	4	64
	20	14	6	124

图10 优化性能测试

Fig. 10 Performance optimization test

参考文献 28

[1]	HE D， WANG S， ZHOU X， et al. An efficient framework for correctness-aware kNN queries on road networks ［C］// Proceedings of the IEEE 35th International Conference on Data Engineering. Piscataway： IEEE， 2019： 1298-1309.
[2]	KUHN H W. The Hungarian method for the assignment problem［J］. Naval Research Logistics Quarterly， 1955， 2（1/2）： 83-97.
[3]	DIJKSTRA E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik， 1959， 1（1）： 269-271.
[4]	PAPADIAS D， ZHANG J， MAMOULIS N， et al. Query processing in spatial network databases ［C］// Proceedings of the 29th Annual International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers Inc.， 2003： 802-813.
[5]	WANG H， ZIMMERMANN R. Snapshot location-based query processing on moving objects in road networks ［C］// Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2008： 1-4.
[6]	MOURATIDIS K， YIU M L， PAPADIAS D， et al. Continuous nearest neighbor monitoring in road networks ［C］// Proceedings of the 32nd International Conference on Very Large Data Bases. ［S.l.］： VLDB Endowment， 2006： 43-54.
[7]	陈国祥，于自强，赵浩宇. 面向动态路网的移动对象分布式k近邻查询算法［J］. 计算机应用， 2024， 44（11）： 3403-3410.
	CHEN G X， YU Z Q， ZHAO H Y. Distributed k-nearest neighbor query algorithm for moving objects in dynamic road network ［J］. Journal of Computer Applications， 2024， 44（11）： 3403-3410.
[8]	SAFAR M. K nearest neighbor search in navigation systems ［J］. Mobile Information Systems， 2005， 1（3）： 207-224.
[9]	OUYANG D， WEN D， QIN L， et al. Progressive top-k nearest neighbors search in large road networks ［C］// Proceedings of the 2020 SIGMOD International Conference on Management of Data. New York： ACM， 2020： 1781-1795.
[10]	LUO S， KAO B， LI G， et al. TOAIN： a throughput optimizing adaptive index for answering dynamic kNN queries on road networks ［J］. Proceedings of the Very Large Data Bases Endowment， 2018， 11（5）： 594-606.
[11]	LEE K C K， LEE W C， ZHENG B， et al. ROAD： a new spatial object search framework for road networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2012， 24（3）： 547-560.
[12]	ZHONG R， LI G， TAN K L， et al. G-tree： an efficient index for kNN search on road networks ［C］// Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. New York： ACM， 2013： 39-48.
[13]	MA H， TANG Y. An efficient and scalable method for aggregate nearest neighbor queries on time-dependent road networks［J］. Information Systems， 2022， 105： No.101925.
[14]	SHEN B， ZHAO Y， LI G， et al. V-Tree： efficient kNN search on moving objects with road-network constraints ［C］// Proceedings of the IEEE 33rd International Conference on Data Engineering. Piscataway： IEEE， 2017： 609-620.
[15]	YU Z， YU X， ZHOU T， et al. ODIN： object density aware index for CkNN queries over moving objects on road networks ［J］. IEEE Transactions on Knowledge and Data Engineering， 2024， 36（11）： 6758-6772.
[16]	韩士元，何清，于自强，等. 面向移动对象连续k近邻查询的双层索引结构［J］. 软件学报， 2023， 34（6）： 2789-2803.
	HAN S Y， HE Q， YU Z Q， et al. Double layer index for continuous k-nearest neighbor queries on moving objects ［J］. Journal of Software， 2023， 34（6）： 2789-2803.
[17]	烟台大学. 一种路网环境下的多目标连续搜索方法及系统：202411237754.9［P］. 2024-10-11.
	Yantai University. Multi-objective continuous search method and system in road network environment： 202411237754.9［P］. 2024-10-11.
[18]	HUANG X， JENSEN C S， LU H， et al. S-GRID： a versatile approach to efficient query processing in spatial networks ［C］// Proceedings of the 2007 International Symposium on Spatial and Temporal Databases， LNCS 4605. Berlin： Springer， 2007： 93-111.
[19]	CAO B， HOU C， LI S， et al. SIMkNN： a scalable method for in-memory kNN search over moving objects in road networks ［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（10）： 1957-1970.
[20]	TANG K， DONG Z， SHI W， et al. A dynamic grid index for CkNN queries on large-scale road networks with moving objects［J］. Applied Sciences， 2023， 13（8）： No.4946.
[21]	LI J， NI C， HE D， et al. Efficient kNN query for moving objects on time-dependent road networks ［J］. The VLDB Journal， 2023， 32（3）： 575-594.
[22]	YAN C， CHEN Q. A novel parallel processing for continuous k-nearest neighbor queries ［C］// Proceedings of the 2009 International Conference on Environmental Science and Information Application Technology — Volume 1. Piscataway： IEEE， 2009： 593-596.
[23]	REZA R M， ALI M E， HASHEM T. Group processing of simultaneous shortest path queries in road networks ［C］// Proceedings of the 16th IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2015： 128-133.
[24]	YAN D， ZHAO Z， NG W. Efficient processing of optimal meeting point queries in Euclidean space and road networks ［J］. Knowledge and Information Systems， 2015， 42（2）： 319-351.
[25]	CHUNG Y C， SU I F， LEE C， et al. Multiple k nearest neighbor search ［J］. World Wide Web， 2017， 20（2）： 371-398.
[26]	GIESEKE F， OANCEA C E， MAHABAL A， et al. Bigger buffer k-d trees on multi-many-core systems ［C］// Proceedings of the 2018 International Conference on Vector and Parallel Processing， LNCS 11333. Cham： Springer， 2019： 202-214.
[27]	CHO H J， ATTIQUE M. Group processing of multiple k-farthest neighbor queries in road networks ［J］. IEEE Access， 2020， 8： 110959-110973.
[28]	KARYPIS G， KUMAR V. A fast and high quality multilevel scheme for partitioning irregular graphs ［J］. SIAM Journal on Scientific Computing， 1998， 20（1）： 359-392.

路网环境下移动对象冲突k近邻查询

Conflict-aware k-nearest neighbor query over moving objects in road networks

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 28

相关文章 15

编辑推荐

Metrics

[1]	赵浩宇, 于自强, 陈晓萌, 陈国祥, 朱慧, 李博涵. 支持关键词搜索的top-K条最优路线查询问题[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2455-2465.
[2]	陈国祥, 于自强, 赵浩宇. 面向动态路网的移动对象分布式k近邻查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3403-3410.
[3]	马永强, 陈晓萌, 于自强. 分布式环境下大规模移动对象范围查询算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 111-121.
[4]	包玄, 陈红梅, 肖清. 融入时间的兴趣点协同推荐算法[J]. 计算机应用, 2021, 41(8): 2406-2411.
[5]	张豪, 朱睿, 宋栿尧, 方鹏, 夏秀峰. 距离-关键字相似度约束的双色反k近邻查询方法[J]. 计算机应用, 2021, 41(6): 1686-1693.
[6]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[7]	徐江峰, 谭玉龙. 基于HBase的多维索引查询机制的优化[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 571-577.
[8]	付宇, 王红. 位置隐私保护的虚拟轨迹填充算法[J]. 计算机应用, 2019, 39(8): 2318-2325.
[9]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[10]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[11]	李琰, 刘嘉勇. 基于作者主题模型和辐射模型的用户位置预测模型[J]. 计算机应用, 2018, 38(4): 939-944.
[12]	李佳佳, 刘晓静, 刘向宇, 夏秀峰, 朱睿. 基于动态选择启发值的改进TD-FTT算法[J]. 计算机应用, 2018, 38(1): 120-125.
[13]	赵大鹏, 宋光旋, 靳远远, 王晓玲. 基于查询概率的位置隐私保护方法[J]. 计算机应用, 2017, 37(2): 347-351.
[14]	吕绍仟, 孟凡荣, 袁冠. 基于轨迹结构的移动对象热点区域发现[J]. 计算机应用, 2017, 37(1): 54-59.
[15]	周沙, 王润, 甄文杰. 顾及主观判断延误的行人路径选择模型[J]. 计算机应用, 2016, 36(4): 1146-1150.