本发明涉及最短路线查询，尤其是涉及一种动态图top-k最优路线的分布式查询方法及系统。
背景技术：
1、道路网络环境下的top-k最优路线（即查找多条最优路线）查询问题在现实生活中极为重要。许多基于位置的服务如自动驾驶、打车服务、外卖配送等均涉及top-k最优路线的查找，目的是为用户提供多条可供选择的导航路线。该问题中，道路网络可以抽象为图模型，其中，每个路口看做一个顶点，路口与路口之间的路段看作对应顶点之间的边，路段的通行时间看作图中对应边的权重。现实中，道路通行时长随时间持续变化，图中对应边的权重也就不断变化，整个道路网络则被表示为边的权重不断变化的为动态图。因此道路网络环境下top-k条最优路线的搜索问题的本质为动态图top-k最优路线查询问题。该问题是指给定一个动态图（graph g）和一个包含起点和终点构成的top-k路线查询q，查找和之间最短的k条路线（无环路），每条路线的长度为该路线经过的所有边的权重之和。实际应用中，动态图的top-k路线查询问题通常具有两个特征：
2、（1）要求实时响应，对查询效率要求极高，减少用户的在线等待时间；
3、（2）很多应用场景下（如早晚高峰期），查询并发量大，且短时间内可能急剧增长。
4、近年来，图的top-k最优路线查询问题被广泛研究，但是绝大多数方法是基于单个计算节点的集中式查询算法，查询效率低，可扩展性差，难以支持高并发的top-k最优路线查询；此外，已有方法大多研究静态图的top-k最优路线查询问题，通过构建最短路线索引以提高top-k最优路线的搜索效率；然而，当该类方法被应用于动态图时，预先构建的最短路线索引将会失效，难以支撑动态图的大规模top-k最优路线查询的高效处理。
技术实现思路
1、为了解决上述提到的问题，本发明提供一种动态图top-k最优路线的分布式查询方法及系统。本发明能够对动态图上的top-k最优路线查询问题分解为若干动态子图上的局部top-k最优路线搜索问题，易于在分布式环境下进行并行化处理，从而提高top-k最优路线查询效率。此外，本发明所提出的方法具备良好的可扩展性，能够有效应对海量并发top-k最优路线查询。
2、第一方面，本发明提供的一种动态图top-k最优路线的分布式查询方法，采用如下的技术方案：
3、一种动态图top-k最优路线的分布式查询方法，包括：
4、获取动态图；
5、基于动态图建立分布式动态两级索引结构，即dtlp索引；
6、基于dtlp索引，利用dg-ksp算法计算得到top-k最优路径。
7、进一步地，所述基于动态图建立分布式动态两级索引结构，即dtlp索引，包括以宽度优先的方法将动态图划分为多个子图，不同子图共享顶点；根据子图边的权重信息，计算子图边界点之间的最小边界距离，建立子图索引；根据子图索引构建骨架图索引。并根据边的权重变化信息，对dtlp索引结构进行更新。
8、进一步地，所述根据子图边的权重信息，计算子图边界点之间的最小边界距离，建立子图索引，包括以下步骤：
9、（1）计算子图中各个边界点之间的边界路径、边界距离；
10、（2）计算子图中各个边界点之间的最小边界距离，构建第一级子图索引；
11、（3）利用子图索引中的边界点与最小边界距离，构建第二级骨架图gλ索引；
12、（4）根据边的权重变化信息，依次更新子图索引和骨架图索引，实现dtlp索引的维护。
13、进一步地，所述基于dtlp索引，利用dg-ksp算法计算得到top-k最优路径，包括利用查询处理算子与骨架图索引交互，得到由查询起点、终点和子图边界点组成的参照路径；所述查询处理算子根据边界点所在的子图，与对应的子图索引算子交互，获得top-k最优路线在各子图对应的部分；查询处理算子将基于每对边界点所在子图包含的局部top-k最优路线组合，获得完整的top-k最优路线。
14、进一步地，所述查询处理算子根据参照路径任意两个相邻边界点所在的子图，与对应的子图索引算子交互，获得top-k最优路线该子图中对应的局部路线。
15、进一步地，所述查询处理算子将任意两个相邻边界点之间局部top-k最优路线组合，获得完整的top-k最优路线，包括查找包含相邻边界点的子图，计算两个相邻边界点之间在该子图中的top-k最优路径，再将所有相邻边界点间的top-k最优路径合并，形成完整的top-k最优路径。
16、第二方面，一种动态图top-k最优路线的分布式查询系统，包括：
17、数据分发模块，用于实时接入连续到达的权重数据和最短路径查询，根据分布式动态两级索引结构，将权重和top-k最优路径查询分别分发至子图管理模块和查询处理模块；
18、子图管理模块，用于存储其所负责的相应子图，计算子图的最小边界距离数据，建立子图索引，并实时维护更新权重的索引结构；
19、骨架图gλ管理模块，负责对骨架图gλ的实时更新和维护，分别与子图管理模块、查询处理模块之间进行索引数据交互；
20、查询处理模块，根据dg-ksp查询算法处理top-k最优路径查询请求。
21、第三方面，本发明提供一种计算机可读存储介质，其中存储有多条指令，所述指令适于由终端设备的处理器加载并执行所述的一种动态图top-k最优路线的分布式查询方法。
22、第四方面，本发明提供一种终端设备，包括处理器和计算机可读存储介质，处理器用于实现各指令；计算机可读存储介质用于存储多条指令，所述指令适于由处理器加载并执行所述的一种动态图top-k最优路线的分布式查询方法。
23、综上所述，本发明具有如下的有益技术效果：
24、（1）本发明采用的面向大型动态图上top-k最优路径查询的分布式计算平台具备分布式的子图管理模块和查询处理模块，能够很好地支撑本发明所提出的分布式动态两级索引结构，满足大型动态图上top-k最优路径查询的分布式访问需求，避免不同算子在处理时大型动态图上top-k最优路径查询时出现数据错发问题，为大型动态图上top-k最优路径查询提供了通用的分布式计算平台；
25、（2）本发明所提出的分布式动态两级索引结构能够对持续变化的大型动态图上边的权重数据进行实时存储和维护；此外，该索引结构具备良好的可扩展性，在分布式环境下，仅通过增加硬件资源就可以实现索引结构时空数据处理能力的线性增长；最后，该索引结构能够很好地支持dg-ksp查询算法，在很大程度上加速了ds-ksp查询算法的收敛；
26、（3）本发明利用dg-ksp算法来实现对大型动态图上top-k最优路径查询的实时处理，减少了分布式环境下处理大型动态图上top-k最优路径查询所产生的物理计算节点之间的通信代价，能够对大型动态图上top-k最优路径查询进行实时响应，查询效率显著提高。
1.一种动态图top-k最优路线的分布式查询方法，其特征在于，包括：
2.根据权利要求1所述的一种动态图top-k最优路线的分布式查询方法，其特征在于，所述基于动态图建立分布式动态两级索引结构，即dtlp索引，包括以宽度优先的方法将动态图划分为多个子图，不同子图共享顶点；根据子图边的权重信息，计算子图边界点之间的最小边界距离，建立子图索引，并根据子图索引构建骨架图索引。
3.根据权利要求2所述的一种动态图top-k最优路线的分布式查询方法，其特征在于，所述基于动态图建立分布式动态两级索引结构，即dtlp索引，还包括根据边的权重变化信息，对 索引进行更新。
4.根据权利要求3所述的一种动态图top-k最优路线的分布式查询方法，其特征在于，所述根据子图索引构建骨架图索引，包括以下步骤：
5.根据权利要求4所述的一种动态图top-k最优路线的分布式查询方法，其特征在于，所述基于dtlp索引，利用dg-ksp算法计算得到top-k最优路径，包括利用查询处理算子与骨架图索引交互，得到由查询起点、终点和子图边界点组成的参照路径；所述查询处理算子根据边界点所在的子图，与对应的子图索引算子交互，获得top-k最优路线在各子图对应的部分；查询处理算子将基于每对边界点所在子图包含的局部top-k最优路线组合，获得完整的top-k最优路线。
6.根据权利要求5所述的一种动态图top-k最优路线的分布式查询方法，其特征在于，所述查询处理算子根据参照路径任意两个相邻边界点所在的子图，与对应的子图索引算子交互，获得top-k最优路线该子图中对应的局部路线。
7.根据权利要求6所述的一种动态图top-k最优路线的分布式查询方法，其特征在于，所述查询处理算子将基于每对边界点所在子图包含的局部top-k最优路线组合，获得完整的top-k最优路线，包括查找包含相邻边界点的子图，计算两个相邻边界点之间在该子图中的top-k最优路径，再将所有相邻边界点间的top-k最优路径合并，形成完整的top-k最优路径。
8.一种动态图top-k最优路线的分布式查询系统，其特征在于，包括：
9.一种计算机可读存储介质，其中存储有多条指令，其特征在于，所述指令适于由终端设备的处理器加载并执行如权利要求1所述的方法。
10.一种终端设备，包括处理器和计算机可读存储介质，处理器用于实现各指令；计算机可读存储介质用于存储多条指令，其特征在于，所述指令适于由处理器加载并执行如权利要求1所述的方法。
