Enhanced reach-based graph processing using shortcuts

• US 7,774,734 B2
• Filed: 11/06/2006
• Issued: 08/10/2010
• Est. Priority Date: 11/06/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Werneck, Renato F., Goldberg, Andrew V., Kaplan, Haim
• Primary Examiner(s): Levin; Naum B
• Application Number:
  US11/593,857
• Publication Number:
  US 20080122848A1
• Time in Patent Office: 1,373 Days
• Field of Search: 716 12- 14, 701201-203, 701/209
• US Class Current: 716/129
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

An algorithm referred to as REAL for the point-to-point shortest path problem combines A* search with landmark-based lower bounds and reach-based pruning. A symbiosis of these techniques is described, which gives a range of time and space tradeoffs, including those that improve both of these complexity measures. Locality is improved and exact reach computation is described.

Claims

1. A computer-implemented method of graph preprocessing, the method comprising:

receiving as input a graph comprising a plurality of vertices and arcs;

recursively processing, via the computer, a set of vertices of said graph that includes vertices with high vertex reaches using an iterative process which comprises;

adding shortcut arcs to the graph;

eliminating one or more vertices in the graph that are bypassed by an added shortcut arc; and

storing a preprocessed graph comprising the added shortcut arcs.

2. The method of claim 1, further comprising setting a constant value, α

, wherein the vertices in the set of the vertices comprise 1/α

of the plurality of vertices with a highest reach.

3. The method of claim 1, further comprising partitioning the plurality of vertices into two sets of vertices, wherein a first set of the vertices comprises a predetermined fraction of vertices among the plurality of vertices of the graph having a highest reach.

4. The method of claim 3, further comprising retaining the original ordering of the vertices in each of the two sets prior to the recursively processing.

5. The method of claim 4, wherein the recursively processing comprises re-ordering the first set of vertices and placing high-reach vertices close to each other in memory to optimize cache locality.

6. The method of claim 1, wherein eliminating one or more vertices comprises identifying vertices that are bypassable and eliminating bypassable vertices.

7. The method of claim 1, further comprising eliminating the arcs associated with the eliminated vertices.

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

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

10. The method of claim 1, wherein the method is implemented for reach-based processing in a P2P (point-to-point) application.

11. A computer readable storage medium comprising program instructions that are executable by a computer to perform method steps for graph preprocessing, the method steps comprising:

receiving as input a graph comprising a plurality of vertices and arcs;

recursively processing a set of vertices that includes vertices with high vertex reaches using an iterative process which comprises;

adding shortcut arcs to the graph; and

eliminating one or more vertices in the graph that are bypassed by an added shortcut arc; and

storing a preprocessed graph comprising the added shortcut arcs.

12. The computer readable storage medium of claim 11, further comprising program instructions for setting a constant value, α

, wherein the vertices in the first set of the vertices comprise 1/α

of the plurality of vertices with a highest reach.

13. The computer readable storage medium of claim 11, further comprising program instructions for partitioning the plurality of vertices into two sets of vertices, wherein a first set of the vertices comprises a predetermined fraction of vertices among the plurality of vertices of the graph having a highest reach.

14. The computer readable storage medium of claim 13, further comprising program instructions for retaining the original ordering of the vertices in each of the two sets prior to the recursively processing.

15. The computer readable storage medium of claim 14, wherein the program instructions for recursively processing comprise program instructions for re-ordering the first set of vertices and placing high-reach vertices close to each other in memory to optimize cache locality.

16. The computer readable storage medium of claim 11, wherein the program instructions for eliminating one or more vertices comprise program instructions for identifying vertices that are bypassable and eliminating bypassable vertices.

17. The computer readable storage medium of claim 11, further comprising program instructions for eliminating the arcs associated with the eliminated vertices.

18. The computer readable storage medium of claim 11, wherein the graph represents a network of nodes.

19. The computer readable storage medium of claim 11, wherein the graph represents a road map.

20. A computing system, comprising:

a processing unit;

system memory for storing a P2P (point-to-point) application program comprising program instructions that are executable by the processing unit to perform a method for preprocessing a graph, said method comprising;

receiving as input a graph comprising a plurality of vertices and arcs;

recursively processing a set of vertices that include vertices with high vertex reaches using an iterative process which comprises;

adding shortcut arcs to the graph; and

eliminating one or more vertices in the graph that are bypassed by an added shortcut arc; and

storing a preprocessed graph comprising the added shortcut arcs.