Providing routing information based on ambiguous locations

• US 7,571,048 B2
• Filed: 08/18/2006
• Issued: 08/04/2009
• Est. Priority Date: 08/18/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Komatsu, Hiroyuki
• Primary Examiner(s): To; Tuan C
• Application Number:
  US11/465,771
• Publication Number:
  US 20080082256A1
• Time in Patent Office: 1,082 Days
• Field of Search: 701/201, 340/988, 340/995.22, 340/905, 340/995, 455/89, 455/404.2, 455/428, 455/445, 455/456.1
• US Class Current: 701/201
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services

Abstract

A routing server receives a request for routing information. The request specifies one or more locations. A specified location may be ambiguous. For an ambiguous location, the routing server identifies a set of potentially-matching locations and ranks the locations according to a metric. The routing server returns routing information for the highest-ranked location that potentially matches an ambiguous location. If a request for routing information specifies two locations, and at least one location is ambiguous, the routing server pairs combinations of potentially-matching locations based on the query and calculates a metric for each pair. In one case, the metric is the distance between the locations in the pair. The routing server ranks the pairs based on the metric, and returns routing information for the highest-ranked pair.

Claims

1. A computer-implemented method of providing routing information, comprising:

receiving, by a computer, a request for routing information, the request specifying at least one ambiguous location;

identifying, by a computer, locations potentially matching the ambiguous location;

ranking, by a computer, the potentially-matching locations based on a metric; and

providing, by a computer, routing information for the highest-ranked potentially-matching location.

2. The method of claim 1, wherein the metric is distance, and wherein the ranking comprises:

calculating a distance between each location potentially matching the ambiguous location and an other location; and

ranking the potentially-matching locations based on the distances from the potentially-matching locations to the other location.

3. The method of claim 2, wherein the highest-ranked potentially-matching location has the shortest distance to the other location.

4. The method of claim 1, wherein the metric is populations of the potentially-matching locations.

5. The method of claim 1, wherein the metric is frequencies that the potentially-matching locations appear in routing requests.

6. The method of claim 1, wherein the ranking comprises:

generating pairings of locations based on locations specified in the request, each pairing including at least one location potentially matching the ambiguous location;

calculating distances between the locations in the pairs; and

ranking the pairings based on the calculated distances.

7. The method of claim 1, wherein the routing information comprises one or more types of information from the set consisting of:

driving directions, train schedules, bus schedules, and flight schedules.

8. The method of claim 1, wherein the ambiguous location is a starting or ending location of a route for which routing information is requested.

9. A system for providing routing information, comprising:

a computer-readable storage medium storing executable computer program modules comprising;

a request receipt module for receiving a request for routing information, the request specifying at least one ambiguous location;

a location lookup module for identifying locations potentially matching the ambiguous location;

an ambiguous location ranking module for ranking the potentially-matching locations based on a metric; and

a reporting module for providing routing information for the highest-ranked potentially-matching location; and

a processor for executing the computer program modules.

10. The system of claim 9, wherein the metric is distance, and wherein the ambiguous location ranking module is further adapted to:

calculate a distance between each location potentially matching the ambiguous location and an other location; and

rank the potentially-matching locations based on the distances from the potentially-matching locations to the other location.

11. The system of claim 10, wherein the highest-ranked potentially-matching location has the shortest distance to the other location.

12. The system of claim 9, wherein the metric is populations of the potentially-matching locations.

13. The system of claim 9, wherein the metric is frequencies that the potentially-matching locations appear in routing requests.

14. The system of claim 9, wherein the ambiguous location ranking module is further adapted to:

generate pairings of locations based on locations specified in the request, each pairing including at least one location potentially matching the ambiguous location;

calculate distances between the locations in the pairs; and

rank the pairings based on the calculated distance.

15. The system of claim 9, wherein the routing information comprises one or more types of information from the set consisting of:

driving directions, train schedules, bus schedules, and flight schedules.

16. A computer program product having a computer-readable storage medium having executable computer program code tangibly embodied therein for providing routing information, comprising:

a request receipt module for receiving a request for routing information, the request specifying at least one ambiguous location;

a location lookup module for identifying locations potentially matching the ambiguous location;

an ambiguous location ranking module for ranking the potentially-matching locations based on a metric; and

a reporting module for providing routing information for the highest-ranked potentially-matching location.

17. The computer program product of claim 16, wherein the metric is distance, and wherein the ambiguous location ranking module is further adapted to:

calculate a distance between each location potentially matching the ambiguous location and an other location; and

rank the potentially-matching locations based on the distances from the potentially-matching locations to the other location.

18. The computer program product of claim 17, wherein the highest-ranked potentially-matching location has the shortest distance to the other location.

19. The computer program product of claim 16, wherein the metric is populations of the potentially-matching locations.

20. The computer program product of claim 16, wherein the metric is frequencies that the potentially-matching locations appear in routing requests.

21. The computer program product of claim 16, wherein the ambiguous location ranking module is further adapted to:

generate pairings of locations based on locations specified in the request, each pairing including at least one location potentially matching the ambiguous location;

calculate distances between the locations in the pairs; and

rank the pairings based on the calculated distance.

22. The computer program product of claim 16, wherein the routing information comprises one or more types of information from the set consisting of:

driving directions, train schedules, bus schedules, and flight schedules.

23. A computer-implemented method of providing routing information, comprising:

receiving, by a computer, a request for routing information, the request specifying at least one ambiguous location;

identifying, by a computer, locations potentially matching the ambiguous location;

ranking, by a computer, the potentially-matching locations based on a metric;

selecting, by a computer, a potentially-matching location based on the ranking; and

providing, by a computer, routing information for the selected location.