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

Top-K optimal route query problem with keyword search support

作　　者：赵浩宇 于自强 陈晓萌 陈国祥 朱慧 李博涵[2] ZHAO Haoyu;YU Ziqiang;CHEN Xiaomeng;CHEN Guoxiang;ZHU Hui;LI Bohan(School of Computer and Control Engineering,Yantai University,Yantai Shandong 264005,China;College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing Jiangsu 211106,China)

机构地区：[1]烟台大学计算机与控制工程学院,山东烟台264005 [2]南京航空航天大学计算机科学与技术学院,南京211106

出　　处：《计算机应用》2024年第8期2455-2465,共11页journal of Computer Applications

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

摘　　要：支持关键词搜索的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%。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 o

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

分 类 号：TP392[自动化与计算机技术—计算机应用技术]