Computing systems, devices and methods for identifying important access roads to a geographic location

• US 8,831,882 B1
• Filed: 05/15/2013
• Issued: 09/09/2014
• Est. Priority Date: 05/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: John, John Payyappillil, Chawathe, Yatin, Lee, Nicholas, Qing Wu, Matthew Zhong, Gonterman, Chris, Morgan-Linial, Ross
• Primary Examiner(s): Olszewski, John R
• Assistant Examiner(s): Ziaeianmehdizadeh, Navid
• Application Number:
  US13/895,043
• Time in Patent Office: 482 Days
• Field of Search: None
• US Class Current: 701/533
• CPC Class Codes: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence

Abstract

To identify important access roads for a geographic location, multiple previous requests for directions between a multiplicity of sources and one or more destinations identical, or proximate, to the geographic location are identified. Further, routes between the multiplicity of sources and the one or more destinations are determined. Still further, common road segments shared by at least some of the determined routes are identified, and a set of important access roads for the geographic location are selected from among the identified road segments based on how frequently the identified road segments are used.

Claims

1. A method in a computing system for identifying important access roads for a geographic location, the method comprising:

identifying, by one or more processors, a plurality of previous requests for directions between a multiplicity of sources and one or more destinations identical, or proximate, to the geographic location;

determining, by the one or more processors, routes between the multiplicity of sources and the one or more destinations;

identifying, by the one or more processors, (i) a first road segment that is commonly shared by at least two of the determined routes, and (ii) a second road segment that is commonly shared by at least two additional of the determined routes;

determining, by the one or more processors, that the first road segment is used more frequently than the second road segment; and

designating, by the one or more processors, the first road segment as an important access road for the geographic location.

2. The method of claim 1 implemented in a server operating in a communication network, the method further comprising:

repeating the acts of (i) determining routes, (ii) identifying a first and second road segments, (iii) determining frequency of use, and (iv) designating the first road segment as an important access road for a plurality of geographic locations including the geographic location; and

storing the designated important access road for the plurality of geographic locations in a database.

3. The method of claim 2, further comprising:

subsequently to storing the designated important access roads for the plurality of geographic locations in the database, receiving a request for important access roads from a client device, wherein the request specifies the geographic location;

in response to receiving the request, retrieving the designated important access roads for the geographic location from a database; and

providing the retrieved designated important access roads to the client device.

4. The method of claim 1, wherein identifying the plurality of previous requests for directions between the multiplicity of sources and the one or more destinations includes:

identifying a number of requests in which the one or more destinations are identical to the geographic location,

in response to determining that the number of requests exceeds a threshold value, determining at least a portion of the routes that are between the multiplicity of sources and the geographic location,

otherwise, in response to determining that the number of requests is below the threshold value, (i) selecting a geographic area that encloses the geographic location, (ii) determining at least a portion of the routes that are between the multiplicity of sources and multiple destinations within the geographic area, and (iii) identifying the first and second road segments that are commonly shared and that terminate at a boundary of the geographic area.

5. The method of claim 4, further comprising determining a size of the geographic area based on population density near the geographic location.

6. The method of claim 1, wherein determining the routes includes requesting driving directions according to a fastest route option.

7. The method of claim 1, wherein the important access road is within a predetermined radius of the geographic location.

8. The method of claim 1, wherein the important access road connects the geographic location to one or more high-speed roads.

9. A method in a computing system for identifying important access roads for a geographic location, the method comprising:

selecting, by one or more processors, a geographic area that encloses the geographic location;

identifying, by the one or more processors, previous requests for directions between a multiplicity of sources and a plurality of destinations within the geographic area;

determining, by the one or more processors, routes between the multiplicity of sources and a boundary of the geographic area;

identifying, by the one or more processors, a first road segment that is commonly shared by at least two of the determined routes, and (ii) a second road segment that is commonly shared by at least two additional of the determined routes;

determining, by the one or more processors, that the first road segment is used more frequently than the second road segment; and

designating, by the one or more processors, the first road segment as an important access road for the geographic area.

10. The method of claim 9, wherein selecting the geographic area is in response to determining that a number of previous requests for directions to the geographic location is below a threshold value.

11. The method of claim 9, wherein the important access road terminates at a point on the boundary of the geographic area;

and wherein the method further comprises;

determining at least one additional route between the point and the geographic location.

12. The method of claim 11, wherein:

the designating of the first road segment as the important access road is implemented in a batch process scheduled independently of the selection of the geographic area, and

the determining of the at least one additional route between the point and the geographic location is implemented in real time in response to a user selecting the geographic location via a user interface.