Hardware accelerated shortest path computation

• US 8,364,717 B2
• Filed: 01/10/2011
• Issued: 01/29/2013
• Est. Priority Date: 01/10/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Delling, Daniel, Goldberg, Andrew V., Nowatzyk, Andreas, Werneck, Renato F.
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US12/987,176
• Publication Number:
  US 20120179674A1
• Time in Patent Office: 750 Days
• Field of Search: 707/798
• US Class Current: 707/798
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

The non-negative single-source shortest path (NSSP) problem is solved on a graph by using a preprocessing phase and then, in a query phase, computing the distances from a given source in the graph with a linear sweep over all the vertices. Contraction hierarchies may be used in the preprocessing phase and in the query phase. Optimizations may include reordering the vertices in advance to exploit locality, performing multiple NSSP computations simultaneously, marking vertices during initialization, and using parallelism. Techniques may be performed on a graphics processing unit (GPU). This makes applications based on all-pairs shortest-paths practical for continental-sized road networks. The applications include, for example, computing graph diameter, exact arc flags, and centrality measures such as exact reaches or betweenness.

Claims

1. A method for graph preprocessing, comprising:

receiving as input, at a computing device, a graph comprising a plurality of vertices and arcs;

performing contraction hierarchies on the graph, by the computing device, to generate shortcuts between at least some of the vertices;

assigning levels to each of the vertices, by the computing device; and

storing data corresponding to the vertices, the shortcuts, and the levels, as preprocessed graph data in storage associated with the computing device.

2. The method of claim 1, further comprising ordering the vertices into an order prior to performing the contraction hierarchies on the graph, wherein the contraction hierarchies are performed based on the order.

3. The method of claim 2, further comprising storing data corresponding to the order as a portion of the preprocessed graph data.

4. The method of claim 2, wherein ordering the vertices comprises ordering the vertices based on a measure of importance of the vertices.

5. The method of claim 2, further comprising reordering the vertices after performing the contraction hierarchies on the graph.

6. The method of claim 1, wherein the graph represents a network of nodes.

7. The method of claim 1, wherein the graph represents a road map.

8. The method of claim 1, wherein the method is implemented for a non-negative single-source shortest path application.

9. A method for determining distances on a graph, comprising:

preprocessing, at a computing device, a graph comprising a plurality of vertices to generate data corresponding to the vertices, a plurality of shortcuts between at least a portion of the vertices, a plurality of levels associated with the vertices, and an order of the vertices to generate preprocessed graph data;

receiving a query at the computing device;

determining a source vertex based on the query, by the computing device;

performing, by the computing device, a plurality of non-negative single-source shortest path computations on the preprocessed data with respect to the source vertex to determine the distances between the source vertex and a plurality of other vertices in the graph; and

outputting the distances, by the computing device.

10. The method of claim 9, wherein performing the non-negative single-source shortest path computations comprises:

performing an upwards contraction hierarchies search from the source vertex to generate a plurality of arcs; and

performing a linear sweep over the arcs.

11. The method of claim 10, wherein performing the upwards contraction hierarchies search comprises setting distance labels of each of the plurality of vertices.

12. The method of claim 10, wherein performing the linear sweep comprises scanning the plurality of vertices in a descending rank order.

13. The method of claim 10, further comprising:

marking each of the vertices with a single bit responsive to the upwards contraction hierarchies search;

checking for the single bit during the linear sweep; and

setting the distance label for each of the vertices based on whether or not the vertex is marked with the single bit.

14. The method of claim 10, wherein the computing device comprises a CPU and a GPU, and the upwards contraction hierarchies search is performed by the CPU and the linear sweep is performed by the GPU.

15. The method of claim 9, wherein the plurality of non-negative single-source shortest path computations are performed simultaneously.

16. A method for determining distances on a graph, comprising:

receiving as input, at a computing device, preprocessed graph data representing a graph comprising a plurality of vertices, wherein the preprocessed data corresponds to the vertices, a plurality of shortcuts between at least a portion of the vertices, a plurality of levels associated with the vertices, and an order of the vertices, wherein the preprocessed graph data is generated using contraction hierarchies on the graph;

performing, by the computing device, a plurality of shortest path computations on the preprocessed graph data with respect to a source vertex to determine the distances between the source vertex and a plurality of other vertices in the graph, wherein the plurality of shortest path computations use a contraction hierarchies search; and

outputting the distances, by the computing device.

17. The method of claim 16, wherein the plurality of shortest path computations comprises a plurality of non-negative single-source shortest path computations.

18. The method of claim 16, further comprising generating the preprocessed graph data comprising:

receiving as input the graph comprising the plurality of vertices;

ordering the vertices into an order;

performing the contraction hierarchies on the graph based on the order to generate shortcuts between at least some of the vertices;

assigning levels to each of the vertices; and

storing data corresponding to the vertices, the shortcuts, the order, and the levels, as the preprocessed graph data in storage associated with the computing device.

19. The method of claim 16, wherein the method is implemented for a non-negative single-source shortest path application.

20. The method of claim 19, wherein the method is implemented for an application that determines graph diameter, determines exact arc flags, determines an exact reach of a vertex, or determines exact betweenness.