Computing point-to-point shortest paths from external memory

• US 20060047421A1
• Filed: 04/27/2005
• Published: 03/02/2006
• Est. Priority Date: 08/25/2004
• Status: Abandoned Application

• Current Assignee: Dong AHM Bio-Tech Co., Ltd., Ke H.O. Lee, Microsoft Technology Licensing LLC (Microsoft Corporation), Sang-Bum Lee
• Original Assignee: Microsoft Corporation
• Inventors: Goldberg, Andrew V., Werneck, Renato
• Application Number:
  US11/115,558
• Publication Number:
  US 20060047421A1
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops

Abstract

Methods and systems are provided for computing shortest paths among a set of locations. A set of landmarks is dynamically selected by starting with two original landmarks and then improving the landmark selection based on distance to other landmarks. The landmarks are then used with A* search to find the shortest path from source to destination. Additional improvements are provided to reduce the amount of storage required. Landmarks may be generated or selected from a subset of landmarks during pre-processing using one or more selection heuristics, such as using tree-based heuristics and using a local search.

Claims

1. A method of finding a shortest path from a starting location to a destination location among a set of locations, comprising:

selecting a set of landmarks;

computing distances between each landmark and locations within the set of locations;

computing lower bounds based on the distances; and

running an A* process based on the lower bounds to determine the shortest path.

2. The method of claim 1, wherein selecting the set of landmarks comprises selecting the set of landmarks using an avoid landmark selection method.

3. The method of claim 2, further comprising optimizing the avoid landmark selection method using a local search method.

4. The method of claim 1, wherein selecting the set of landmarks comprises selecting the set of landmarks using a maxcover selection method.

5. The method of claim 1, wherein the A* process uses active landmarks.

6. The method of claim 5, further comprising dynamically selecting the active landmarks.

7. The method of claim 6, wherein dynamically selecting the active landmarks comprises:

determining whether the best lower bound on the distance from a landmark to a destination location is at least a predetermined factor better than a current lower bound; and

if so, activating the landmark.

8. A landmark selection method comprising:

determining the sizes of a plurality of vertices corresponding to a plurality of locations;

traversing a first tree graph starting from the vertex having the largest size and following a child with the largest size, until a leaf is reached; and

activating the leaf as a landmark.

9. The method of claim 8, further comprising determining a second tree graph rooted at a vertex, and determining the weight of every vertex in the second tree graph, prior to determining the sizes of the plurality of vertices.

10. The method of claim 9, wherein determining the weight of each vertex comprises determining the difference between the actual shortest path and the lowest bound on the second tree graph.

11. The method of claim 9, wherein the sizes of the plurality of vertices is based on a subtree of the second tree graph rooted at the vertex whose size is being determined.

12. The method of claim 8, further comprising performing a local search on the landmark.

13. A landmark selection method comprising:

a) determining a plurality of landmarks;

b) adding the landmarks to a set of candidates;

c) discarding the landmarks having a predetermined probability;

d) generating additional landmarks;

e) adding the additional landmarks that are not already in the set to the set of candidates; and

f) repeating steps (c)-(e) until a predetermined condition is met.

14. The method of claim 13, wherein steps (a) and (d) comprises using an avoid landmark selection process.

15. The method of claim 13, wherein the predetermined probability is ½

.

16. The method of claim 13, wherein the predetermined condition is one of the set of candidates reaches a predetermined size and step (d) is executed a predetermined number of times.

17. The method of claim 13, further comprising (g) executing a maxcover selection process using the set of candidate landmarks.