Better landmarks within reach

• US 20080122848A1
• Filed: 11/06/2006
• Published: 05/29/2008
• Est. Priority Date: 11/06/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Goldberg, Andrew V., Kaplan, Haim, Werneck, Renato F.
• Granted Patent: US 7,774,734 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• 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 method of graph preprocessing, comprising:

receiving a graph, the graph comprising a plurality of vertices and arcs; and

recursively processing a first set of the vertices by generating shortcuts to the graph, and eliminating one or more vertices pursuant to the shortcuts.

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

, wherein the first set of the vertices comprises the 1/α

fraction of vertices with a highest reach.

3. The method of claim 1, further comprising partitioning the plurality of vertices into two sets, wherein the first set of the vertices comprises a predetermined fraction of vertices 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 1, wherein the recursively processing comprises re-ordering the first set of vertices and placing high-reach vertices close to each other.

6. The method of claim 1, wherein the recursively processing comprises identifying and eliminating bypassable vertices.

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

8. A method of query processing, comprising:

storing landmark distances for vertices of a graph, the vertices having a reach of at least a predetermined amount;

receiving a query; and

processing the query using a bidirectional technique based on the predetermined amount of the reach.

9. The method of claim 8, further comprising setting the predetermined amount to equal a reach threshold.

10. The method of claim 8, wherein the bidirectional technique comprises a bidirectional Dijkstra algorithm that uses two search areas.

11. The method of claim 10, wherein processing the query comprises reach pruning without using A* search.

12. The method of claim 10, wherein processing the query comprises processing until both search areas have a radius of at least the predetermined amount.

13. The method of claim 12, further comprising, after both search areas have a radius of at least the predetermined amount, using a combination of reach pruning and A* search.

14. A method of graph preprocessing, comprising:

receiving a graph, the graph comprising a plurality of vertices and arcs;

dividing the graph into a plurality of regions;

determining a plurality of full shortest path trees from the frontier of each region; and

determining a plurality of partial shortest path trees from internal vertices of trees rooted at the frontier of each region.

15. The method of claim 14, further comprising determining a reach for each arc.

16. The method of claim 15, further comprising eliminating a plurality of arcs from the graph based on the reach for each arc.

17. The method of claim 16, further comprising selecting the arcs for elimination based on a comparison of the reach for each arc with a predetermined reach threshold.

18. The method of claim 17, further comprising repeating the preprocessing until the graph is free of arcs.

19. The method of claim 18, further comprising adding shortcuts to the graph.

20. The method of claim 19, wherein the shortcuts comprise reducing the reach of the vertices.