关键词覆盖最优路径查询（Keyword-aware Optimal Route Query,KOR）查找满足关键词全覆盖和路径长度约束条件下,时间开销最小的路线,是旅行规划、路径导航等应用的高频查询。尽可能地缩短KOR的执行时间是KOR优化的最主要目标。现有算法的优化主要是采用高效的路径拓展剪枝策略,缩小搜索空间,降低算法复杂度,但是在查找长路径时,由于搜索深度大,搜索规模的增加依然过大。针对现有算法固有的拓展规模难以控制,长路径搜索执行时间长的问题,本文提出关键词最优路径查询的分段拓展算法SE-KOR（Segmentation expansion algorithm for keyword-aware optimal route query）。SE-KOR根据关键词倒排列表构建关键词顶点路径,然后将路径以关键词顶点为边界划分为多段,逐段拓展,降低搜索规模（深度）,从而缩短执行时间。由于SE-KOR在路径拓展时已给出路径走向,而现有剪枝策略不控制路径拓展方向,因此提出局部代价阈值剪枝,控制路径的走向沿关键词顶点路径拓展,并综合运用近似支配、可行解目标值剪枝和全局优先拓展策略,加速拓展。在SE-KOR的基础上,路径拓展并行化是进一步缩短长路径KOR执行时间的有效途径,其关键是如何把逐段拓展,改为同时拓展。本文提出关键词最优路径查询的分段并行拓展算法PSE-KOR（Segmented parallel expansion algorithm for keyword-aware optimal route query）。PSE-KOR根据关键词顶点的个数计算并行度,以相应的关键词顶点为边界,将路径分段,对于每个分段,提出适应并行拓展的可行解目标值剪枝策略和局部代价阈值降低路径之间的关联度和搜索深度,然后并行拓展,进一步缩短执行时间。除此之外,受并行拓展的启发,为进一步加速整个KOR查询过程,本文在数据预处理阶段进行并行操作,缩短预处理时间。并进一步提出分布式预处理方法,实现同时处理多张路网图的功能。本文创新点如下:（1）针对现有算法在面临长路径搜索执行时间长的问题,提出关键词最优路径查询的分段拓展算法（SE-KOR）。该算法以关键词顶点为边界点,将路径分为多段,逐段拓展,降低搜索深度,从而降低搜索规模,缩短执行时间。（2）针对现有剪枝策略不控制路径拓展方向的问题,提出局部代价阈值剪枝,控制路径的走向沿着关键词顶点路径的方向拓展。（3）为进一步缩短长路径KOR的执行时间,提出关键词最优路径查询的分段并行拓展算法（PSE-KOR）。PSE-KOR根据关键词顶点的个数计算并行度,以相应的关键词顶点为边界,将路径分段,利用适应并行拓展的可行解目标值剪枝策略和局部代价阈值降低路径之间的关联度和搜索深度,然后并行拓展。（4）针对预处理耗时长的问题,将串行的预处理操作并行化,并提出分布式预处理方案,实现同时处理多张路网图的操作,进一步加速整个KOR的求解过程。本文从查询关键词数量、代价阈值、误差因子ε和优先级因子β四个方面与现有算法对比。通过一系列实验验证,在保证近似度的前提下,SE-KOR的平均执行时间至少比对比算法KSRG缩短17.5%,PSE-KOR的平均执行时间至少比SE-KOR缩短7.4%。