一种关键词最优路径查询的分段并行拓展方法

技术领域

本发明属于空间数据查询技术领域，具体是一种关键词最优路径查询的分段并行拓展方法。

背景技术

随着人们对旅游路径需求的多样化，路径查询不只是常见的最短路径查询，人们往往会综合考虑其他因素，如路径时间开销和路径覆盖的兴趣点。考虑如下的场景：当用户想要去某些地方旅游，希望找到一条从指定地点出发，途经满足用户指定的兴趣点，最后到达终点的路径，该路径在满足游客的行程预算(以下称为代价阈值)的前提下，所用时间越短越好。上述查询称为关键词最优路径查询(Keyword-aware Optimal Route Query，KOR)。KOR是一种满足关键词全覆盖、代价阈值(路径长度)和目标值(时间开销)最小的路径查询。该查询通常用于旅行规划、路径导航和其他应用程序。

缩短执行时间是KOR优化的重要目标，但现在存在两个挑战。第一个挑战是降低搜索规模。现有最先进的技术要么利用邻边拓展，它本质上是从起点开始逐个顶点遍历；或者采用关键词顶点拓展，跳过与关键词无关的顶点不断拓展相邻顶点以外的关键词顶点，但该方法需要在预处理中计算精简Skyline路径，时空开销巨大。虽然上述两种方法在拓展时采用各种剪枝策略来缩短执行时间，如近似支配剪枝、全局优先级拓展、可行解目标值剪枝、最小代价值剪枝等，但它们的搜索规模随着路径长度或搜索深度的增加呈指数增长，执行时间仍然令人难以接受。

第二个挑战是将现有的路径拓展方法与剪枝策略相结合，以进一步缩短执行时间。目前最先进的技术本质上是串行拓展，即在查询阶段或预处理阶段一次拓展一个顶点，但该方法已达到其性能壁垒。并行拓展路径或许是一个不错的选择。相关研究已经证实单约束下最短路径并行路径拓展的可行性，例如并行拓展单源最短路径和全源最短路径。但目前对于多约束最短路径并行拓展的研究尚未涉及。

现有技术存在以下问题：

(1)长路径搜索时，现有算法的搜索规模随路径长度或者搜索深度的增加呈指数增长，执行时间过长。

(2)并行拓展技术多应用于单约束条件下的最短路径查询，还未涉及到如KOR问题的多约束路径查询的研究。为实现KOR问题的并行拓展，本发明需探索如何将串行的多约束拓展并行化。

发明内容

本发明为了解决上述问题，提供一种关键词最优路径查询的分段并行拓展方法。

本发明采取以下技术方案：一种关键词最优路径查询的分段并行拓展方法，包括以下步骤。

S100：计算查询图中任意两顶点间的最小代价值b(v

S200：关键词倒排列表构建：将顶点的所有关键词信息{v.w

S300：跳过与查询关键词无关的顶点，构建目标值最小的关键词顶点路径记为

S400：对关键词顶点路径进行划分，并对划分后的路径分段并行拓展。

步骤S300包括以下步骤，

S310：给定一个查询

S320：在关键词顶点查询图G′中，将关键词顶点排列组合，通过广度优先搜索对其遍历，最终返回满足关键词全覆盖和代价阈值的

步骤S320包括以下步骤，给定一个查询

S321：首先在v

S322：从起点开始向所有关键词顶点拓展，并构建从v

S323：选取全局优先级最高的标签

S324：继续选取优先级别最高的标签拓展，重复过程S323，直至拓展至终点v

S325：继续选取优先级别最高的标签拓展，重复过程S323，直至拓展至终点v

步骤S322中，标签

进行步骤S400前，对步骤S300中构建的目标值最小的关键词顶点路径

在构建

1)

2)

3)

步骤S400具体包括以下步骤，

S410：设置并行度，将关键词顶点路径划分为多段，关键词顶点路径中除首尾顶点外的所有顶点都是关键词顶点，使用关键词顶点对路径进行分割。

S420：对路径分段进行并行拓展，在拓展路径分段时，判断从起始点顶点经过非关键词顶点到每段路径的目标顶点的所有路径的代价值是否小于等于目标顶点处的局部代价阈值，若是且不被近似支配，则进行适用并行拓展的可行解目标值剪枝策略对比，若符合判断条件，则计算全局优先度后入队，否则被舍弃。

步骤S410中，设置并行度的原则是使各个路径分段中的关键词顶点尽量均匀以便拓展时各个路径分段中的顶点数相近，从而达到各路径分段的拓展时间接近的目的；在实际并行时，可以根据关键词顶点路径的中的关键词顶点的个数或者通过衡量每段局部代价阈值的大小设置并行度。

步骤S420中，可行解目标值剪枝策略对比的判断不等式为：

其中，

与现有技术相比，本发明具有以下有益效果：

(1)本发明提供了一种将多约束KOR问题转换为受限最短路径问题的思路，即首先构建满足关键词全覆盖和代价阈值的关键词顶点路径，然后在详细拓展中考虑目标值最小约束，将问题进行切分。

(2)本发明针对长路径搜索执行时间长的问题，提出关键词最优路径查询的分段并行拓展方法(PSE-KOR)，通过构建关键词顶点路径，然后以关键词顶点为边界将路径划分为多段，降低长路径搜索时的搜索规模(深度)，然后采用并行拓展的方式，进一步缩短长路径KOR的执行时间。

(3)对于每个分段的路径拓展，提出局部代价阈值剪枝来约束拓展方向和搜索深度，同时降低各分段路径之间的关联度。同时利用近似支配剪枝、全局优先级拓展和适用并行拓展的可行解目标值剪枝策略，加速拓展。

附图说明

图1为查询图结构图；

图2为关键词顶点路径示意图；

图3为关键词顶点路径的构建示意图；

图4为关键词顶点路径示例。

具体实施方式

本发明针对上述问题，提供了一种关键词最优路径查询的分段并行拓展方法，该方法首先跳过与查询关键词无关的顶点，仅对关键词顶点拓展，构建关键词顶点路径；然后以关键词顶点为边界，将路径划分为多段，并行拓展，最后拼接成完整路径。为降低各路段之间的关联度、降低搜索规模，本发明还提出局部代价阈值和适用于并行拓展的可行解目标值剪枝，配合并行拓展。

在进一步说明之前，首先对KOR定义进行说明：

KOR基于路网，路网可以抽象成如图1所示的查询图。

定义1查询图：G＝(V,E)由顶点集V和边集E构成。任意v∈V表示兴趣点，v的地理位置用经纬度表示，记为v.loc，v的关键词集合表示为

如图1所示，通常代价值表示边的长度，用括号外的数值表示；目标值表示经过边所需要的时间，用括号内的数值表示。表1列出图1中各顶点对应的关键词集合。

表1顶点关键词信息

定义2路径：p＝(v

根据定义2，路径p的代价值和目标值分别为：

定义3KOR：一个KOR查询Q是一个四元组

下面对本发明的技术方案做进一步说明：

S100：利用Floyd算法，计算查询图中任意两顶点间的最小代价值b(v

S200：关键词倒排索引构建：将兴趣点的所有关键词信息{v.w

表2关键词倒排索引表

S300：跳过与查询关键词无关的顶点，构建目标值最小的关键词顶点路径记为

定义4关键词顶点：给定

定义5关键词顶点路径：给定

步骤S300包括以下步骤：

S310：给定一个查询

简化的关键词顶点查询图G′如图2所示。虚线连接关键词顶点，形成关键词顶点查询图。

S320：在关键词顶点查询图G′中，将关键词顶点排列组合，通过广度优先搜索对其遍历，最终返回满足关键词全覆盖和代价阈值的

S320：在关键词顶点查询图G′中，将关键词顶点排列组合，通过广度优先搜索对其遍历，最终返回满足关键词全覆盖和代价阈值的

步骤S320包括以下步骤，给定一个查询

S321：首先在v

S322：从起点开始向所有关键词顶点拓展，并构建从v

标签

S323：选取全局优先级最高的标签

代价阈值：路径在满足游客的行程预算。

近似支配：假设给定一个参数α，α稍大于1(如α＝1.1)，若路径p

目标修正：给定查询图G＝(V,E)和查询

S324：继续选取优先级别最高的标签拓展，重复过程S323，直至拓展至终点v

S325：继续选取优先级别最高的标签拓展，重复过程S323，直至拓展至终点

拓展结果体现在图4所示的G′中，v

对步骤S300中构建的目标值最小的关键词顶点路径

在构建

(1)

(2)

(3)

o

由上文可知，在构建

S400：对关键词顶点路径进行划分，并对划分后的路径分段并行拓展。具体步骤如下：

S410：设置并行度，将关键词顶点路径划分为多段，关键词顶点路径中除首尾顶点外的所有顶点都是关键词顶点，使用关键词顶点对路径进行分割。

关键词顶点路径中除首尾顶点外的所有顶点都是关键词顶点，因此可以使用关键词顶点对路径进行分割。如图4所示，路径

设置并行度的原则是使各个路径分段中的关键词顶点尽量均匀以便拓展时各个路径分段中的顶点数相近，从而达到各路径分段的拓展时间接近的目的；在实际并行时，可以根据关键词顶点路径的中的关键词顶点的个数或者通过衡量每段局部代价阈值的大小设置并行度。

S420：对路径分段进行并行拓展，在拓展路径分段时，判断从起始点顶点经过非关键词顶点到每段路径的目标顶点的所有路径的代价值是否小于等于目标顶点处的局部代价阈值，若是且不被近似支配，则进行适用并行拓展的可行解目标值剪枝策略对比，若符合判断条件，则计算全局优先度后入队，否则被舍弃。

可行解目标值剪枝：当获取一条可行路径p

局部代价阈值：已知一条关键词顶点路径

由于构建关键词顶点路径时，已经满足关键词全覆盖和代价阈值这两个约束条件，并且记录了每段路径的局部代价阈值，因此在并行拓展每段路径时可以使用局部代价阈值代替全局代价阈值约束。局部代价阈值仅对每段路经进行约束，与其他路径是独立的，因此可以降低路径之间的关联度。可行解目标值剪枝策略对比的判断不等式为：

其中，