本发明涉及信息，尤其涉及一种大规模多属性道路交通网络上的线性最短路径索引方法。
背景技术：
1、图是一种用来表征复杂关系的数据结构，经常用来抽象地表示事物间的联系和性质。最短路径查询是图上的一个基本问题，在现实世界中有着广泛的应用，且已经得到了很好的研究。然而现有的关于最短路径问题的研究，大多是基于单属性图(或单代价图，在下文中，不影响理解的情况下我们将代价与属性交替使用)，即边上只有一个属性(代价)，也只能研究单个属性的最优化。但是我们生活的世界有着很多能够影响我们决定的因素，例如在道路交通网络上，现有研究多是追求最短的道路长度，而实际需求更为复杂，我们会考虑交通时间(一般与道路长度成正相关，且我们一般期待较少的交通时间)，路径上的车流量(一般与道路长度成负相关，因为人们总是偏向于选择更短的路，但我们一般期待较少的车流量，因为发生事故的概率较小，更为安全)，单位长度上的景观数目(与道路长度无直接关系，但我们一般希望其值更大)等相关因素，而且对于不同的人有着不同的偏好，即所有属性有着不同的权重分配，如果按照单个属性查询，结果往往不能满足人们的多方面需求。所以我们需要整合不同的属性，按照人们不同的偏好来推荐路径。
2、因此，通过用户给定的任意对应图上各属性的权重以模拟不同用户对于不同属性或代价的偏好或接受程度，快速返回用户给定权重下的最优路径具有重要意义。
技术实现思路
1、本发明目的就是为了弥补已有技术的缺陷，提供一种大规模多属性道路交通网络上的线性最短路径索引方法，本发明可以在大规模多代价交通网络上构建线性最短路径索引，从而在用户给出图上各属性代价权重的条件下快速返回最优路径。
2、本发明是通过以下技术方案实现的：
3、一种大规模多属性道路交通网络上的线性最短路径索引方法，所述方法包括：
4、101：利用图分区方法对道路交通网络图g进行划分，将其分割成多个子图
5、
6、102：对每个子图进行树分解并在分解的过程中构建分区内部的结点线性天际线索引；
7、在分区之间构建索引，即构建所有边界结点到各分区的最短距离；
8、在构建索引的过程中使用凸包合并和多级分区的方法加快构建；
9、103：利用构建好的索引通过点定位的方法查询在给出的用户偏好权重下的最优解。
10、其中，所述图分区解释如下：所述的道路交通网络是一个d-维多代价道路交通网络mcrn，表示为无向连接图g＝(v,e,w)，其中v是顶点集合,是边集合，是一个张量；让|v|和|e|分别为顶点数目和边数目，每条边e∈e和一个w里的d-维代价向量w(e)＝(w1,w2,…,wd)相对应,其中w(e)i＝wi≥0是e的第i个代价值，使用自然割的方法将图进行划分，将给定的图g＝(v,e),划分成一系列子图g1＝(v1,e1),g2＝(v2,e2),…,gk＝(vk,ek)s.t，v1,v2,…vk是v的划分，道路交通网络上的边与代价向量的对应关系保持不变。u、v表示图中的结点，是数学中的符号，表示“任意”，就代表任意两个在vi中的结点u和v，vi表示第i个图gi的结点集(即它的全部结点)，ei表示第i个图gi的边集(即它的全部边)本发明使用自然割的方法对道路交通网络图进行分区；
11、步骤102所述的对每个子图进行树分解并在分解的过程中构建分区内部的结点线性天际线索引，具体如下：
12、对于图的每个分区，首先按照结点的度数对分区内结点进行收缩，保存结点在当前图的邻居结点，记录其到当前邻居结点的线性天际线并形成树节点；
13、从分区中删除顶点v，并记录删除顶点的顺序；
14、当分区内所有结点都被收缩之后，将每个分区的内部结点组织作为若干棵树，记录每个树节点的父亲和孩子结点关系，然后按照自顶向下的方式，对于每棵树上的结点，以其邻居结点为中继结点计算其到树根的邻居结点的线性天际线，从而形成每个分区内结点到边界结点的索引；
15、最后，对于每个边界结点，计算其到所有分区的所有单代价最短距离作为启发式函数，引导在边界图上进行的在线搜索。
16、其中，树分解和索引构建过程参考单维度树分解和索引构建方法h2h，但由于本发明应用于多维度图，本发明使用的方法与h2h有三点不同，具体为：
17、(1)在最小度消除(mde)过程中，本发明维护的并不是最短距离信息，而是线性天际线的完整信息。相比于dp-图，本发明需要在过程中维护线性天际线保存图以防止线性天际线信息的丢失。因此本发明需要在这个过程执行大量的凸包计算。
18、(2)本发明不会对分区的边界结点进行收缩，而且对于每个分区内的结点只会维护到分区边界结点的线性天际线信息，而不会维护到树分解上其他祖先节点的信息。这是出于对索引规模控制的考虑，如果存储空间允许，也可以维护到其他祖先节点的线性天际线信息以加速分区内查询。当所有分区内结点都收缩之后，会留下一些边界结点，本发明将这些边界结点构成的图定义为边界图。
19、(3)由于分区内部结点不一定连续，对某个分区构建的树分解结果也不一定只有一棵树，例如对分区进行树分解后该分区内会形成两棵树，这样需要存储的到边界结点的索引变少。
20、其中，在分区之间构建索引，即为记录所有边界结点到各分区的最短距离；
21、其中，凸包合并指的是，在索引构建过程中包含了大量的凸包计算，而对于任意一个凸包pl(v,w)，满足于也构成了凸包，直观解释就是把pl(v,w)凸包按照向量p的方向整体移动了，但仍构成凸包。因此，可以将部分凸包计算改为合并|pl(u,v)|个将pl(v,w)移动后的凸包。
22、其中，多级分区指的是用多级分区来加速大型图上远距离点对的查询，建立更高一层的分区，类似于，如果存储空间允许，本发明技术允许建立像g-tree的距离矩阵一样的线性天际线矩阵以存储任意两边界之间的线性天际线，否则仅仅存储所有边界结点到所在上一层分区的边界结点的线性天际线。
23、步骤103所述的利用构建好的索引通过点定位的方法查询在给出的用户偏好权重下的最优解，即在给定的线性天际线里查询用户偏好权重向量w下的最优解，具体如下：
24、本发明通过一个映射，将其映射为d-1维的结构，并把查询最优变为计算几何中的点定位问题。映射过程为，查询哪个线性天际线点在w下最优时只需要查询w′落在哪个区域内，w′为w前d-1维组成的向量，从而解决将线性天际线中的每个点与w进行点积，之后遍历查询颇费时间，缺乏效率的问题。
25、所述的最优路径查询，对于同一分区内的两个内部结点，按照用户给定的偏好权重向量，与每个结点边上的代价向量进行点积使得变为代价值，然后使用dijkstra进行查询，该过程可以直接得到完整路径以及距离信息，不需要进行额外的的路径恢复；如果是两个不同分区的点，或其中一个是同分区的边界点，则根据l(s)和l(t)以及边界图gb＝(vb,eb)，构建边界图的扩展图g′b＝(v′b,e′b)，使用边界结点到其他分区的单代价最短距离信息作为启发函数进行a*搜索，其中v′b＝vb∪s,t,e′b＝eb∪{(v,r.vertex)|v∈s,tvb,r∈l(v)}，新增边上对应的线性天际线由相应r中存储的线性天际线给出。l(s)、l(t)表示算法3所构建的索引，是多条路径的集合，l(s)就表示从s出发所有可以到达的点的路径以及对应的代价。公式中的r∈l(v)代表r是集合l(v)中的一个元素，即r是某一条路径，而路径就会有起始点和到达点，所以r.vertex就表示r这条路径的两个端点(起始点和到达点)，a*全称a*搜索算法，是计算机领域广为人知的经典算法。
26、所述的最优路径路径查询，其过程中会遇到一些只存储了距离信息，而没有完整的路径信息，对于路径信息的恢复，根据得到的包含边界结点的路径p＝(s,b1,b2,…,bk,t)进行完整路径补充，即对于任意两个p中相邻的点a,b，无论是两个边界结点，还是一个边界节点一个分区内结点，都有两点间的线性天际线信息，因此从a开始，找到其所有的邻居结点中属于完整路径中的结点，再以该节点进行扩展，直到b；判断在完整路径上的邻居结点的方法是：通过判断邻居结点v是否满足dist(a,v)+dist(v,b)＝dist(a,b),其中dist(a,b)表示在a到b的线性天际线中根据点定位找到的最优代价向量与用户给定的偏好向量w的点积，即在w下a到b的最短距离。
27、本发明的优点是：1、本发明提出了一个可并行化的新的索引用于解决lsp问题，以及优化方法加速查询效率，并分析了维度增高带来的问题与解决思路；
28、2、本发明提出了一种了图分区+树分解的方法为大规模道路交通网络图构建索引，由于这个方法在不同分区上构建索引的过程是互不影响的，所以可以并行化，同时在多个分区构建索引；
29、3、本发明提出了两种用于优化索引构建速度的方法，分别是凸包合并和多级分区，有利于在大规模道路交通网络图上快速的构建线性天际线索引。
1.一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，具体包括如下步骤：
2.根据权利要求1所述的一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，所述的道路交通网络是一个d-维多代价道路交通网络mcrn，表示为无向连接图g＝(v,e,w)，其中v是顶点集合,是边集合，是一个张量；让|v|和|e|分别为顶点数目和边数目，每条边e∈e和一个w里的d-维代价向量w(e)＝(w1,w2,…,wd)相对应,其中w(e)i＝wi≥0是e的第i个代价值，使用自然割的方法将图进行划分，将给定的图g＝(v,e),划分成一系列子图g1＝(v1,e1),g2＝(v2,e2),…,gk＝(vk,ek)s.t，v1,v2,…vk是v的划分，道路交通网络上的边与代价向量的对应关系保持不变，u、v表示图中的结点，代表任意两个在vi中的结点u和v，vi表示第i个图gi的结点集，ei表示第i个图gi的边集。
3.根据权利要求2所述的一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，步骤102所述的对每个子图进行树分解并在分解的过程中构建分区内部的结点线性天际线索引，具体如下：
4.根据权利要求3所述的一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，步骤102中构建分区内部的结点线性天际线索引时使用凸包合并和多级分区的方法加快索引的构建。
5.根据权利要求4所述的一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，所述的凸包合并指的是，在索引构建过程中包含了大量的凸包计算，而对于任意一个凸包pl(v,w)，满足于也构成了凸包，即把pl(v,w)凸包按照向量p的方向整体移动，但仍构成凸包；因此，将部分凸包计算改为合并|pl(u,v)|个将pl(v,w)移动后的凸包。
6.根据权利要求4所述的一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，所述的多级分区指的是用多级分区来加速大型图上远距离点对的查询，建立更高一层的分区，即如果存储空间允许，建立线性天际线矩阵以存储任意两边界之间的线性天际线，否则仅仅存储所有边界结点到所在上一层分区的边界结点的线性天际线。
7.根据权利要求4所述的一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，步骤103所述的利用构建好的索引通过点定位的方法查询在给出的用户偏好权重下的最优解，即在给定的线性天际线里查询用户偏好权重向量w下的最优解，具体如下：
8.根据权利要求7所述的一种大规模多属性道路交通网络上的线性最短路径索引方法，其特征在于，所述的最优路径路径查询，其过程中会遇到一些只存储了距离信息，而没有完整的路径信息，对于路径信息的恢复，根据得到的包含边界结点的路径p＝(s,b1,b2,…,bk,t)进行完整路径补充，即对于任意两个p中相邻的点a,b，无论是两个边界结点，还是一个边界节点一个分区内结点，都有两点间的线性天际线信息，因此从a开始，找到其所有的邻居结点中属于完整路径中的结点，再以该节点进行扩展，直到b；判断在完整路径上的邻居结点的方法是：通过判断邻居结点v是否满足dist(a,v)+dist(v,b)＝dist(a,b),其中dist(a,b)表示在a到b的线性天际线中根据点定位找到的最优代价向量与用户给定的偏好向量w的点积，即在w下a到b的最短距离。
