支持关键词搜索的top-K条最优路线查询问题

doi:10.11772/j.issn.1001-9081.2023081267

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (8): 2455-2465.DOI: 10.11772/j.issn.1001-9081.2023081267

支持关键词搜索的top-K条最优路线查询问题

赵浩宇¹, 于自强¹(), 陈晓萌¹, 陈国祥¹, 朱慧¹, 李博涵²

^1.烟台大学计算机与控制工程学院，山东烟台 264005
^2.南京航空航天大学计算机科学与技术学院，南京 211106

收稿日期:2023-09-14 修回日期:2023-10-12 接受日期:2023-11-02 发布日期:2024-08-22 出版日期:2024-08-10
通讯作者: 于自强
作者简介:赵浩宇（1999—），男，山东临沂人，硕士研究生，主要研究方向：时空数据处理
于自强（1984—），男，山东青岛人，副教授，博士，CCF会员，主要研究方向：数据库、数据挖掘 zqyu@ytu.edu.cn
陈晓萌（1997—），女，山东淄博人，硕士研究生，主要研究方向：时空数据处理
陈国祥（1998—），男，山东青岛人，硕士研究生，主要研究方向：时空数据处理
朱慧（1998—），女，山东临沂人，硕士研究生，主要研究方向：时空数据处理
李博涵（1979—），男，黑龙江哈尔滨人，副教授，博士，CCF会员，主要研究方向：时空数据处理。
基金资助:
国家自然科学基金资助项目(62172351)

Top-K optimal route query problem with keyword search support

Haoyu ZHAO¹, Ziqiang YU¹(), Xiaomeng CHEN¹, Guoxiang CHEN¹, Hui ZHU¹, Bohan LI²

^1.School of Computer and Control Engineering，Yantai University，Yantai Shandong 264005，China
^2.College of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing Jiangsu 211106，China

Received:2023-09-14 Revised:2023-10-12 Accepted:2023-11-02 Online:2024-08-22 Published:2024-08-10
Contact: Ziqiang YU
About author:ZHAO Haoyu ， born in 1999， M. S. candidate. His researchinterest includes spatial-temporal data processing.
YU Ziqiang ， born in 1984， Ph. D. ， associate professor. Hisresearch interests include database， data mining.
CHEN Xiaomeng， born in 1997， M. S. candidate. Her researchinterest includes spatial-temporal data processing.
CHEN Guoxiang， born in 1998， M. S. candidate. His researchinterest includes spatial-temporal data processing.
ZHU Hui， born in 1998， M. S. candidate. Her research interestincludes spatial-temporal data processing.
LI Bohan， born in 1979， Ph. D. ， associate professor. Hisresearch interest includes spatial-temporal data processing.
Supported by:
This work is partially supported by National Natural ScienceFoundation of China（ 62172351）.

摘要/Abstract

摘要：

支持关键词搜索的top-K条最优路线查询问题是针对给定的道路网络、兴趣点集合、起点和多个关键词的路线查询。查询旨在找到途经与查询关键词匹配的多个兴趣点的k条最优路线。然而，一些现有研究为降低算法的复杂度，将用户输入关键词的顺序作为到达兴趣点顺序，不适用于对兴趣点到达顺序没有要求的场景，降低了实用性；另一些研究为提高查询效率，设定距离阈值对不符合要求的兴趣点剪枝，然而这类算法无法保证被剪枝的兴趣点一定不能组成最优路线。针对上述问题，提出一种关键词感知的top-K最优路线搜索（KKRS）算法。首先，将整个道路网络划分为多个子网络。然后，采用启发式搜索策略从查询起点所在的子网络开始逐步扩展搜索范围，直至找到top-K条最优路线或遍历完整个道路网络。在扩展过程中，引入子图剪枝策略，用于剪去不包含top-K最优路线的子网络，缩小搜索范围。此外，为避免对每个可能构成最优路线的兴趣点集合依次计算，设计兴趣点序列的剪枝策略，以快速过滤不可能构成最优路线的兴趣点序列，降低计算代价。最后，在真实数据集和合成数据集上对提出的两种剪枝算法进行实验，实验结果表明这两种算法在所有数据集上的子图剪枝上都能达到70%以上的剪枝率，在兴趣点序列剪枝上则能保证60%以上的剪枝率。与目前已有的先进算法大规模路网图下关键词覆盖最优路径查询（KORL）、ROSE-GM（Recurrent Optimal Subroute Expansion Using Greedy Merge Strategy）、OSSCaling和StarKOSR（finding Top-K Optional Sequenced Routes with A^*）相比，KKRS算法比对比算法中查询效率较高的StarKOSR算法提高了40%。

关键词: 道路网络, 路线剪枝, 兴趣点, 关键词搜索, 个性化旅游路线

Abstract:

The problems of top-K optimal route query with keyword search support is a route query with given road network， a set of points of interest， a starting point and multiple keywords. The goal of query is to find k optimal routes that pass through multiple points of interest matching the query keywords. However， some existing research simplified the algorithm by using the order of user input keywords as the order of reaching points of interest， which is not suitable for scenarios where there is no requirement for the order of reaching points of interest， thereby reducing practicality. Additionally， some research aims to enhance query efficiency by setting distance thresholds to prune points of interest that do not meet the requirements， but such algorithms cannot guarantee that the pruned points of interest cannot form the optimal route. To address the problems of the above algorithms， a Keyword-aware top-K optimal Routes Search （KKRS） algorithm was proposed. Firstly， the entire road network was divided into multiple subnetworks. Then， a heuristic search strategy was employed to gradually expand the search scope starting from the subnetwork within query’s starting point until the top-K optimal routes were found or the entire road network was traversed. During the expansion process， a subgraph pruning strategy was introduced to remove subnetworks that do not contain the top-K optimal routes， thus reducing the search scope. Furthermore， to avoid computing each potentially optimal set of points of interest one by one， a pruning strategy for the sequence of points of interest was designed to quickly filter out those sequences that cannot form the optimal route， thereby reducing the computational cost. Finally， experiments were conducted on real and synthetic datasets with the two proposed pruning algorithms. These two algorithms achieved the pruning rates of subgraph pruning over 70%， and the pruning rates of points of interest sequence pruning ensured over 60% on all datasets. Compared to the advanced algorithms Keyword-aware Optimal Route query on Large-scale Road Networks （KORL）， ROSE-GM （Recurrent Optimal Subroute Expansion using Greedy Merge Strategy）， OSSCaling， and StarKOSR （finding Top-K Optional Sequenced Routes with A^*）， The KKRS algorithm is 40% more efficient than the StarKOSR algorithm， which is the more query efficient of compared algorithms.

Key words: road network, route pruning, Point Of Interest (POI), keyword search, personalized travel route

中图分类号:

TP392

赵浩宇, 于自强, 陈晓萌, 陈国祥, 朱慧, 李博涵. 支持关键词搜索的top-K条最优路线查询问题[J]. 计算机应用, 2024, 44(8): 2455-2465.

Haoyu ZHAO, Ziqiang YU, Xiaomeng CHEN, Guoxiang CHEN, Hui ZHU, Bohan LI. Top-K optimal route query problem with keyword search support[J]. Journal of Computer Applications, 2024, 44(8): 2455-2465.

图/表 14

表1 本文使用的符号及其含义

Tab. 1 Symbols used in the paper and their meanings

符号	含义
$t i$	第i类关键词
v.loc	顶点v的地理位置坐标
$v . ψ$	顶点v对应的关键词
v.h	顶点v的热度值
$α$	路线距离和兴趣点热度在路线评分中所占比例
$p$	可行路线
$R S (p)$	可行路线p对应的路线评分
$P k$	可行路线集合
SG_i	子图
$b v j$	边界顶点
$G λ$	骨架图
N	扩展已到达的子图所包含的兴趣点集合
$M h$	N中每个 $t i$ 对应最大热度值之和
$T G$	查询点到子图SG的评分上界

表1 本文使用的符号及其含义

Tab. 1 Symbols used in the paper and their meanings

符号	含义
$t i$	第i类关键词
v.loc	顶点v的地理位置坐标
$v . ψ$	顶点v对应的关键词
v.h	顶点v的热度值
$α$	路线距离和兴趣点热度在路线评分中所占比例
$p$	可行路线
$R S (p)$	可行路线p对应的路线评分
$P k$	可行路线集合
SG_i	子图
$b v j$	边界顶点
$G λ$	骨架图
N	扩展已到达的子图所包含的兴趣点集合
$M h$	N中每个 $t i$ 对应最大热度值之和
$T G$	查询点到子图SG的评分上界

图1 路网图G

Fig.1 Road network graph G

图2 子图SG

Fig.2 Subgraph SG

表2 道路网络数据集统计信息

Tab. 2 Statistics of road network datasets

数据集	顶点数	边数	关键词数	兴趣点数
CA	21 048	21 693	64	15 635
BJ	115 436	215 344	173	95 732
NY	264 346	733 846	100	205 427
COL	435 666	1 057 066	100	428 365

表3 实验中使用的参数汇总

Tab. 3 Summary of parameters used in experiments

参数	解释	数值范围（粗体表示默认值）
μ	查询关键词数	2， 4， 6， 8， 10
k	最优路线数	5， 10， 15， 20， 25
α	兴趣点热度值与路线距离在路线评分中的占比	0.2， 0.4， 0.6， 0.8

图3 KKRS算法的构建索引消耗时间和索引所占空间

Fig. 3 Time consumed by index construction and space occupied by indexes

图4 索引对查询时间的影响

Fig.4 Influence of indexes on query time

图5 μ和k对查询时间的影响

Fig. 5 Influence of μ and k on query time

图6 剪枝算法消融实验结果

Fig. 6 Pruning algorithm ablation experiment results

图7 各种参数对剪枝效率的影响

Fig. 7 Influence of various parameters on pruning efficiency

图8 构建索引消耗时间和索引所占空间的对比

Fig. 8 Comparison of time consumed by index construction and space occupied by indexes

表4 不同数据集的查询时间查询效率对比 (ms)

Tab. 4 Query efficiency comparison on different datasets

算法	数据集
算法	CA	BJ	NY	COL
ROSE-GM	276	288	357	579
KORL	170	186	202	385
OSSCaling	449	706	1 052	1 586
KKRS	31	40	44	71
StarKOSR	17	20	27	35
KKRS-LP	12	13	15	23

图9 算法查询时间的对比

Fig. 9 Comparison of algorithm query time

图10 算法可扩展性的对比

Fig. 10 Comparison of algorithm scalability

参考文献 26

1	CHAN H K H， LIU S， LONG C， et al. Cost-aware and distance-constrained collective spatial keyword query［J］. IEEE Transactions on Knowledge and Data Engineering， 2023， 35（2）： 1324-1336.
2	COSTA C F， NASCIMENTO M A， MACÊDO J A F， et al. Optimal time-dependent sequenced route queries in road networks［C］// Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2015： No.56.
3	HASHEM T， HASHEM T， ALI M E， et al. Group trip planning queries in spatial databases［C］// Proceedings of the 2013 International Symposium on Spatial and Temporal Databases， LNCS 8098. Berlin： Springer， 2013： 259-276.
4	KANZA Y， LEVIN R， SAFRA E， et al. Interactive route search in the presence of order constraints［J］. Proceedings of the VLDB Endowment， 2010， 3（1/2）：117-128.
5	LI F， CHENG D， HADJIELEFTHERIOU M， et al. On trip planning queries in spatial databases［C］// Proceedings of the 2005 International Symposium on Spatial and Temporal Databases， LNCS 3633. Berlin： Springer， 2005： 273-290.
6	LI J， YANG Y D， MAMOULIS N. Optimal route queries with arbitrary order constraints［J］. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（5）：1097-1110.
7	LI K， CHEN L， SHANG S. Towards alleviating traffic congestion： optimal route planning for massive-scale trips［C］// Proceedings of the 29th International Joint Conferences on Artificial Intelligence. California： ijcai.org， 2021： 3400-3406.
8	LI K， CHEN L， SHANG S， et al. Traffic congestion alleviation over dynamic road networks： continuous optimal route combination for trip query streams［C］// Proceedings of the 30th International Joint Conferences on Artificial Intelligence. California： ijcai.org， 2021： 3656-3662.
9	LI W， ZHU H， LIU W， et al. Optimal sequenced route query with POI preferences［C］// Proceedings of the 26th International Conference on Database Systems for Advanced Applications， LNCS 12681. Cham： Springer， 2021： 457-473.
10	RICE M N， TSOTRAS V J. Engineering generalized shortest path queries［C］// Proceedings of the IEEE 29th International Conference on Data Engineering. Piscataway： IEEE， 2013： 949-960.
11	ROY S B， DAS G， AMER-YAHIA S， et al. Interactive itinerary planning［C］// Proceedings of the IEEE 27th International Conference on Data Engineering. Piscataway： IEEE， 2011： 15-26.
12	CAO X， CHEN L， CONG G， et al. KORS： keyword-aware optimal route search system［C］// Proceedings of the IEEE 29th International Conference on Data Engineering. Piscataway： IEEE， 2013： 1340-1343.
13	CHEN H， KU W S， SUN M T， et al. The multi-rule partial sequenced route query［C］// Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2008： No.10.
14	LIANG H， WANG K. Top-k route search through submodularity modeling of recurrent POI features［C］// Proceedings of the 41st International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2018： 545-554.
15	ISLAM F T， HASHEM T， SHAHRIYAR R. A privacy-enhanced and personalized safe route planner with crowdsourced data and computation［C］// Proceedings of the 2021 IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021： 229-240.
16	ZENG Y， CHEN X， CAO X， et al. Optimal route search with the coverage of users’ preferences［C］// Proceedings of the 24th International Joint Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2015： 2118-2124.
17	HAO J， NIU B， QIN X. A keyword-aware optimal route query algorithm on large-scale road networks［C］// Proceedings of the 2019 20th IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2019： 587-592.
18	ZHU H， LI W， LIU W， et al. Top-k optimal sequenced route query with poi preferences［J］. Data Science and Engineering， 2022， 7（1）：3-15.
19	LIU H， JIN C， YANG B， et al. Finding top-k optimal sequenced routes［C］// Proceedings of the 2018 IEEE 34th International Conference on Data Engineering. Piscataway： IEEE， 2018： 569-580.
20	郝晋瑶，牛保宁，康家兴. 大规模路网图下关键词覆盖最优路径查询优化［J］. 软件学报， 2020， 31（8）：2543-2556.
	HAO J Y， NIU B N， KANG J X. Optimization of keyword-aware optimal route query on large-scale road networks［J］. Journal of Software， 2020， 31（8）：2543-2556.
21	金鹏飞，牛保宁，张兴忠. 高效的多关键词匹配最优路径查询算法KSRG［J］. 计算机应用， 2017， 37（2）： 352-359.
	JIN P F， NIU B N， ZHANG X Z. KSRG： an efficient optimal route query algorithm for multi-keyword coverage［J］. Journal of Computer Applications， 2017， 37（2）： 352-359.
22	张金增，文洁，孟小峰. 路网环境下访问序列受限的多标签路线查询算法［J］. 计算机学报， 2012， 35（11）：2317-2326.
	ZHANG J Z， WEN J， MENG X F. Multi-tag route query based on order constraints in road networks［J］. Journal of Software， 2012， 35（11）：2317-2326.
23	LARSEN B， AONE C. Fast and effective text mining using linear-time document clustering［C］// Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 1999： 16-22.
24	SHARIFZADEH M， KOLAHDOUZAN M， SHAHABI C. The optimal sequenced route query［J］. The VLDB Journal， 2008， 17（4）： 765-787.
25	SAEKI E， BAO S， TAKAYAMA T， et al. Multi-objective trip planning based on ant colony optimization utilizing trip records［J］. IEEE Access， 2022， 10： 127825-127844.
26	YIU M L， MAMOULIS N， PAPADIAS D. Aggregate nearest neighbor queries in road networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2005， 17（6）：820-833.

[1]	孙晓玲, 王丹辉, 李姗姗. 基于区块链的动态密文排序检索方案[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2500-2505.
[2]	陈国祥, 于自强, 赵浩宇. 面向动态路网的移动对象分布式k近邻查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3403-3410.
[3]	徐则林, 杨敏, 陈勐. 融合空间和文本信息的兴趣点类别表征模型[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2456-2461.
[4]	彭诗杰, 陈红梅, 王丽珍, 肖清. 基于地理偏好排序的兴趣点混合推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2448-2455.
[5]	张笑非, 杨阳, 黄佳进, 钟宁. 基于度中心性的认知特征选择方法[J]. 计算机应用, 2021, 41(9): 2767-2772.
[6]	包玄, 陈红梅, 肖清. 融入时间的兴趣点协同推荐算法[J]. 计算机应用, 2021, 41(8): 2406-2411.
[7]	杨丽, 王时绘, 朱博. 基于动态和静态偏好的兴趣点推荐算法[J]. 计算机应用, 2021, 41(2): 398-406.
[8]	陈凯, 于彦伟, 赵金东, 宋鹏. 基于城市交通监控大数据的工作位置推理方法[J]. 计算机应用, 2021, 41(1): 177-184.
[9]	李寒露, 解庆, 唐伶俐, 刘永坚. 融合时空信息和兴趣点重要性的POI推荐算法[J]. 计算机应用, 2020, 40(9): 2600-2605.
[10]	纪丽娜, 陈凯, 于彦伟, 宋鹏, 王淑莹, 王成锐. 基于城市交通大数据的车辆类别挖掘及应用分析[J]. 计算机应用, 2019, 39(5): 1343-1350.
[11]	邵长城, 陈平华. 融合社交网络和图像内容的兴趣点推荐[J]. 计算机应用, 2019, 39(5): 1261-1268.
[12]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[13]	许朝, 孟凡荣, 袁冠, 李月娥, 刘肖. 融合地点影响力的兴趣点推荐算法[J]. 计算机应用, 2019, 39(11): 3178-3183.
[14]	吴亮, 何毅, 梅雪, 刘欢. 基于时空兴趣点和概率潜动态条件随机场模型的在线行为识别方法[J]. 计算机应用, 2018, 38(6): 1760-1764.
[15]	徐爽, 张谦, 李琰, 刘嘉勇. 基于距离类别的多源兴趣点融合算法[J]. 计算机应用, 2018, 38(5): 1334-1338.

支持关键词搜索的top-K条最优路线查询问题

Top-K optimal route query problem with keyword search support

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 26

相关文章 15

编辑推荐

Metrics