SELECTING LANDMARKS IN SHORTEST PATH COMPUTATIONS

• US 20090228198A1
• Filed: 03/07/2008
• Published: 09/10/2009
• Est. Priority Date: 03/07/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Goldberg, Andrew V., Werneck, Renato F.
• Application Number:
  US12/043,975
• Publication Number:
  US 20090228198A1
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network

Abstract

A set of landmarks may be selected during preprocessing by evaluating a sample of the queries that the landmarks may be used in. A cost function may be used to generate a k-median problem. The k-median problem may then be solved with heuristics. The landmarks may then be used with A* search to find the shortest path from a source to a destination.

Claims

1. A method of determining landmarks for use in computing a shortest path between a start location and a destination location, comprising:

generating a plurality of landmarks;

selecting a plurality of potential queries;

determining a cost for each of a plurality of pairs, each pair comprising one of the landmarks and one of the potential queries;

mapping the landmarks, the potential queries, and the costs to a k-median problem; and

solving the k-median problem for a number of landmarks to use in a plurality of shortest path computations.

2. The method of claim 1, wherein solving the k-median problem comprises using a local search.

3. The method of claim 1, wherein the plurality of landmarks comprises about eight times as many landmarks as the number of landmarks resulting from solving the k-median problem.

4. The method of claim 1, wherein generating the plurality of landmarks comprises selecting the plurality of landmarks within a map, a first portion of the plurality of landmarks selected along a plurality of outer edges of the map and the remaining portion of the plurality of landmarks selected uniformly at random within the map.

5. The method of claim 1, wherein each query in the plurality of potential queries comprises a pair of vertices in a graph and represents finding the path between the vertices in the pair.

6. The method of claim 5, further comprising, for each query, using a triangle inequality to compute a bound on a distance between the two vertices in the query.

7. The method of claim 6, wherein the bound is a lower bound, and further comprising determining a maximum value of the lower bound over the plurality of landmarks.

8. The method of claim 6, wherein the costs are based on the bounds.

9. A method of finding a plurality of shortest paths from a start location to a destination location among a set of locations, comprising:

solving a k-median problem to select a plurality of landmarks; and

running a plurality of shortest path computations to determine the shortest paths based on the plurality of landmarks.

10. The method of claim 9, wherein each shortest path computation comprises an A* search, the A* search being unidirectional or bidirectional.

11. The method of claim 10, further comprising computing lower bounds using the plurality of landmarks, the A* search using the lower bounds to determine the shortest path.

12. The method of claim 9, wherein solving the k-median problem comprises using a local search.

13. The method of claim 9, wherein the plurality of landmarks are selected from a set of landmarks, the set of landmarks comprising a greater number of landmarks than the plurality of landmarks.

14. The method of claim 13, wherein the k-median problem is generated pursuant to a plurality of costs determined for each of a plurality of pairs, each pair comprising one of the set of landmarks and one of a plurality of potential queries.

15. The method of claim 9, further comprising receiving a query comprising the start location and the destination location after solving the k-median problem.

16. A computer-readable medium comprising computer-readable instructions for shortest path computation, said computer-readable instructions comprising instructions that:

determine a cost for each of a plurality of pairs, each pair comprising one of a plurality of previously generated landmarks and one of a plurality of potential queries;

map the landmarks, the potential queries, and the costs to a k-median problem; and

solve the k-median problem for a number of landmarks to use in a shortest path computation between a start location and a destination location.

17. The computer-readable medium of claim 16, wherein the instructions that solve the k-median problem comprise instructions that use a local search heuristic.

18. The computer-readable medium of claim 16, further comprising instructions that perform the shortest path computation responsive to a query comprising the start location and the destination location.

19. The computer-readable medium of claim 18, wherein the instructions that perform the shortest path computation comprise instructions that perform an A* search.

20. The computer-readable medium of claim 16, further comprising instructions that:

generate the plurality of previously generated landmarks; and

select the plurality of potential queries.