作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2022, Vol. 48 ›› Issue (6): 79-88. doi: 10.19678/j.issn.1000-3428.0061722

• 人工智能与模式识别 • 上一篇    下一篇

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

刘蒙蒙, 牛保宁, 杨茸   

  1. 太原理工大学 信息与计算机学院, 山西 晋中 030600
  • 收稿日期:2021-05-24 修回日期:2021-07-20 发布日期:2021-07-29
  • 作者简介:刘蒙蒙(1996—),女,硕士研究生,主研方向为空间数据管理与分析;牛保宁,教授、博士;杨茸,博士。
  • 基金资助:
    国家自然科学基金面上项目(62072326);山西省重点研发计划(国际科技合作)(201903D421007)。

Segmentation Expansion Algorithm for Keyword-Aware Optimal Route Query

LIU Mengmeng, NIU Baoning, YANG Rong   

  1. College of Information and Computer, Taiyuan University of Technology, Jinzhong, Shanxi 030600, China
  • Received:2021-05-24 Revised:2021-07-20 Published:2021-07-29

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

关键词: 多约束, 关键词最优路径查询, 长路径搜索, 分段拓展, 局部代价阈值剪枝

Abstract: 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 breadth-first 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.

Key words: multiple constraint, Keyword-aware Optimal Route query(KOR), long route search, segmentation expansion, local budget constraint pruning

中图分类号: