关键词最优路径查询的分段拓展算法

Segmentation Expansion Algorithm for Keyword-Aware Optimal Route Query

关键词最优路径查询(KOR)查找在满足关键词全覆盖和路径长度约束条件下,时间开销最小的路线常用于旅行规划。现有优化算法虽然采用各种剪枝策略缩小搜索规模,但是本质上是广度优先搜索,在查找长路径时,搜索规模依然过大,执行时间长。针对该问题,提出一种关键词最优路径查询的分段拓展算法(SE-KOR)。SEKOR算法根据关键词倒排索引表构建关键词顶点路径,将路径划分为多段分别拓展,降低搜索规模,从而缩短执行时间。该算法在路径拓展时给出路径走向,而现有剪枝策略不控制路径拓展方向,因此提出局部代价阈值剪枝,控制路径的走向沿关键词顶点路径拓展,并综合运用近似支配、可行解目标值剪枝和全局优先拓展策略加速拓展。实验结果表明,在不损失精度的情况下,该算法执行时间分别在不同关键词个数、代价阈值与查询图规模下至少缩短8.0%、61.0%和57.7%。

The Keyword-aware Optimal Route query(KOR)obtains the route with minimum time overhead under the conditions of full keyword coverage and path length constraints;it is commonly used in travel planning.Although existing optimization algorithms use various pruning strategies to reduce the search scale,they are essentially breadthfirst search schemes.Accordingly,the search scale remains too large and execution time is long when searching for long paths.To address this problem,this studyproposesthe so-called Segmentation Expansion algorithm for a Keyword-aware Optimal Route query(SE-KOR).SE-KOR constructs keyword vertex paths based on the keyword inverted index table,divides the paths into multiple segments to expand them separately,and reduces the search scale.Consequently,it shortens the execution time.Because SE-KOR has a given path direction at the time of path expansion and existing pruning strategies do not control the direction of path expansion,local budget constraint pruning is proposed to control the direction of path expansion along the keyword vertex path.Moreover,a combination of approximate domination,feasible solution objective score pruning,and global priority expansion is used to accelerate the expansion.Experimental results demonstrate that compared with the OSScalling and BucketBound algorithms,the execution time of the algorithm is reduced by at least 8.0%,61.0%,and 57.7% for various keywords,budget constraints,and query graph scales,respectively,without loss of precision.