User queries to model road network usage

• US 9,410,812 B1
• Filed: 07/21/2014
• Issued: 08/09/2016
• Est. Priority Date: 10/06/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadous, Mohammed Waleed, Arfvidsson, Joakim Kristian Olle
• Primary Examiner(s): To, Tuan C.
• Assistant Examiner(s): Mott, Genna
• Application Number:
  US14/336,143
• Time in Patent Office: 750 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• 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/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker

Abstract

A system and method determines a plurality of scores for a road segment that are related to the total distance traveled when drivers traverse that road segment. The scores are displayed graphically to illustrate the usage of road segments. The scores are also used to determine which road segments to display on a map when determining which roads to display at a given zoom level for a map.

Claims

1. A computer-implemented method for displaying roads on a map, comprising:

receiving a plurality of routes traversing road segments between first endpoints and second endpoints on the map, wherein multiple routes traverse a same road segment;

determining a route-based score for the road segment for each of the multiple routes that traverse the road segment, the route-based score for a route based on a first distance from the first endpoint of the route to the road segment and a second distance from the second endpoint of the route to the road segment;

determining a segment score describing usage of the road segment based on the route-based scores;

determining a display threshold for segment scores for the map; and

generating the map for display, the generated map including the road segment responsive to the segment score for the road segment exceeding the threshold.

2. The method of claim 1, wherein determining the route-based score for the road segment comprises:

selecting a highest distance from among the first distance and the second distance; and

using the highest distance as the route-based score.

3. The method of claim 1, wherein determining the segment score of the road segment comprises:

selecting a highest route-based score for the road segment from among the route-based scores; and

using the highest route-based score as the segment score for the road segment.

4. The method of claim 1, wherein the generated map further comprises a graphical representation of the usage of the displayed road segment based on the segment score for the road segment.

5. The method of claim 1 further comprising:

identifying for the road segment adjacent road segments;

selecting a highest segment score from among segment scores of the adjacent road segments;

comparing, for each of the multiple routes that traverse the road segment, the segment score of the road segment to the highest segment score of the adjacent road segments;

selecting the lower of the segment score of the road segment and the highest segment score of the adjacent road segments as an adjusted route-based score for the road segment;

determining an adjusted segment score for the road segment based on the adjusted route-based score for the road segment;

wherein determining the display threshold for segment scores for the map comprises determining a second display threshold for adjusted segment scores; and

wherein the generated map includes road segments having adjusted segment scores exceeding the second display threshold.

6. The method of claim 1, wherein the route-based score is higher if the route is longer.

7. The method of claim 1, wherein the segment score is higher if the routes are longer and wherein the display threshold is higher if an area displayed on the generated map is larger.

8. A system for displaying roads on a map, the system comprising:

a processor configured to execute computer program instructions; and

a non-transitory computer-readable storage medium storing executable computer program instructions for performing steps comprising;

receiving a plurality of routes traversing road segments between first endpoints and second endpoints on the map, wherein multiple routes traverse a same road segment;

determining a route-based score for the road segment for each of the multiple routes that traverse the road segment, the route-based score for a route based on a first distance from the first endpoint of the route to the road segment and a second distance from the second endpoint of the route to the road segment;

determining a segment score describing usage of the road segment based on the route-based scores;

determining a display threshold for segment scores for the map; and

generating the map for display, the generated map including the road segment responsive to the segment score for the road segment exceeding the threshold.

9. The system of claim 8, wherein determining the route-based score for the road segment comprises:

selecting a highest distance from among the first distance and the second distance; and

using the highest distance as the route-based score.

10. The system of claim 8, wherein determining the segment score of the road segment comprises:

selecting a highest route-based score for the road segment from among the route-based scores; and

using the highest route-based score as the segment score for the road segment.

11. The system of claim 8, wherein the generated map further comprises a graphical representation of the usage of the displayed road segment based on the segment score for the road segment.

12. The system of claim 8, wherein the non-transitory computer-readable storage medium further stores executable computer program instructions for performing steps comprising:

identifying for the road segment adjacent road segments;

selecting a highest segment score from among segment scores of the adjacent road segments;

comparing, for each of the multiple routes that traverse the road segment, the segment score of the road segment to the highest segment score of the adjacent road segments;

selecting the lower of the segment score of the road segment and the highest segment score of the adjacent road segments as an adjusted route-based score for the road segment;

determining an adjusted segment score for the road segment based on the adjusted route-based score for the road segment;

wherein determining the display threshold for segment scores for the map comprises determining a second display threshold for adjusted segment scores; and

wherein the generated map includes road segments having adjusted segment scores exceeding the second display threshold.

13. The system of claim 8, wherein the route-based score is higher if the route is longer.

14. The system of claim 8, wherein the segment score is higher if the routes are longer and wherein the display threshold is higher if an area displayed on the generated map is larger.

15. A non-transitory computer readable medium storing executable program code for displaying roads on a map, the program code when executed by a processor performing steps comprising:

receiving a plurality of routes traversing road segments between first endpoints and second endpoints on the map, wherein multiple routes traverse a same road segment;

determining a route-based score for the road segment for each of the multiple routes that traverse the road segment, the route-based score for a route based on a first distance from the first endpoint of the route to the road segment and a second distance from the second endpoint of the route to the road segment;

determining a segment score describing usage of the road segment based on the route-based scores;

determining a display threshold for segment scores for the map; and

generating the map for display, the generated map including the road segment responsive to the segment score for the road segment exceeding the threshold.

16. The non-transitory computer readable medium of claim 15, wherein determining the route-based score for the road segment comprises:

selecting a highest distance from among the first distance and the second distance; and

using the highest distance as the route-based score.

17. The non-transitory computer readable medium of claim 15, wherein determining the segment score of the road segment comprises:

selecting a highest route-based score for the road segment from among the route-based scores; and

using the highest route-based score as the segment score for the road segment.

18. The non-transitory computer readable medium of claim 15, wherein the generated map further comprises a graphical representation of the usage of the displayed road segment based on the segment score for the road segment.

19. The non-transitory computer readable medium of claim 15, wherein the executable program code further comprises code that when executed by a processor performs the steps of:

identifying for the road segment adjacent road segments;

selecting a highest segment score from among segment scores of the adjacent road segments;

comparing, for each of the multiple routes that traverse the road segment, the segment score of the road segment to the highest segment score of the adjacent road segments;

selecting the lower of the segment score of the road segment and the highest segment score of the adjacent road segments as an adjusted route-based score for the road segment;

determining an adjusted segment score for the road segment based on the adjusted route-based score for the road segment;

wherein determining the display threshold for segment scores for the map comprises determining a second display threshold for adjusted segment scores; and

wherein the generated map includes road segments having adjusted segment scores exceeding the second display threshold.

20. The non-transitory computer readable medium of claim 15, wherein the route-based score is higher if the route is longer.

21. The non-transitory computer readable medium of claim 15, wherein the segment score is higher if the routes are longer and wherein the display threshold is higher if an area displayed on the generated map is larger.