Patent Document ID: 9647927
Application ID: 14556355
Patent Status: 1

Claim One:
1. A computer-implemented method for finding the k shortest path lengths among paths between a source vertex and a destination vertex in a data graph composed of vertices interconnected by edges, a path being any series of vertices connected by edges along which path no single vertex is included more than once, the edges being attributed length values, and wherein k is an integer greater than or equal to two, the method including performing a principal process, the principal process comprising performing a computational procedure using a computer, the computational procedure comprising, for the or each vertex preceding a particular vertex, wherein a vertex is defined as preceding the particular vertex if the vertex is connected to the particular vertex by an edge and the vertex lies on one of the paths from a first vertex to the particular vertex: receiving a notification that the computational procedure has been completed for the preceding vertex; and calculating new path lengths for the particular vertex by adding the length value attributed to the edge from the preceding vertex to the particular vertex to each of the recorded k shortest path lengths from the first vertex to the preceding vertex; the computational procedure further comprising: maintaining a record of the k shortest path lengths calculated for the particular vertex; and after the new path lengths have been calculated for the or each of the preceding vertices, issuing a notification that the computational procedure has been completed for the particular vertex; wherein the principal process comprises performing the computational procedure with the source vertex as the first vertex and each vertex on a path from the source vertex to the destination vertex as the particular vertex; wherein the data graph is divided into regions and stored distributed across more than one data storage unit, each data storage unit storing at least one of the regions and having a dedicated computational processing unit, the computational procedure being performed by the computational processing unit dedicated to the data storage unit on which the particular vertex is stored; the method further comprising, concurrently with the principal process, performing a parallel process at each data storage unit, the or each parallel process comprising performing the computational procedure with a parallel process starting vertex as the first vertex and each vertex on a path from the parallel process starting vertex to the parallel process ending vertex as the particular vertex, wherein the parallel process starting vertex and the parallel process ending vertex are both on a path from the source vertex to the destination vertex, wherein the or each of the parallel process starting vertex and the corresponding parallel process ending vertex are from the same region, the parallel process starting vertex being a boundary vertex of the region, and the parallel process is performed for each vertex on any path composed of vertices also in the same region; the method further comprising, for each region: for each vertex at the boundary of the region, storing the vertex in association with the shortest path length from the vertex to the or each of the one or more identified central vertices of each of the other regions; and selecting the parallel process starting vertex for the region by identifying, from among the vertices at the boundary of the region, the vertex having the shortest path length to the or each of the one or more identified central vertices of the region containing the source vertex; the method further comprising: after the issuance of the notification that the computational procedure has been completed for a parallel process starting vertex, from among the one or more parallel process starting vertices, as part of the principal process, and after the issuance of the notification that the computational procedure has been completed for the corresponding parallel process ending vertex as part of the parallel process, modifying the k shortest path lengths from the parallel process starting vertex recorded at each of the vertices for which the computational procedure was performed as part of the parallel process by adding the k shortest path lengths from the source vertex recorded at the parallel process starting vertex.