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

摘要：

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

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