System and method for storing and providing routes

• US 10,247,563 B2
• Filed: 02/22/2017
• Issued: 04/02/2019
• Est. Priority Date: 11/14/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Goel, Vinay
• Primary Examiner(s): Amin, Bhavesh V
• Application Number:
  US15/438,829
• Publication Number:
  US 20170176201A1
• Time in Patent Office: 769 Days
• Field of Search: None
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services

Abstract

In one aspect, a system and method is provided whereby map-related requests from mobile devices are used to store and aggregate routes. The routes are then used to determine optimum directions in response to subsequent requests.

Claims

1. A method, comprising:

receiving, by one or more processors, a plurality of previously traveled routes by a plurality of client devices, each previously traveled route of the plurality of previously traveled routes identifying a route between two or more locations and information identifying streets;

receiving, by the one or more processors from a requesting client device, a request for directions to a destination location, the request identifying a sensor based location determination of the requesting client device;

filtering, by the one or more processors, a subset of previously traveled routes of the plurality of previously traveled routes based on the two or more locations, the destination location, and the sensor based location determination;

selecting, by the one or more processors, a given route of the filtered subset of previously traveled routes based on a total number of client devices that have provided the given route as one or more of the plurality of previously traveled routes;

filtering, by the one or more processors, the given route of the filtered subset of previously traveled routes to remove a given street if the information identifying streets of the plurality of previously traveled routes do not correspond with the given street; and

providing, by the one or more processors, the given route to the requesting client device.

2. The method of claim 1, wherein the given route is further selected based on a time that the request for directions is received.

3. The method of claim 1, wherein the given route is further selected based on user preferences associated with the requesting client device.

4. The method of claim 1, wherein the given route is further selected based on whether the given route has been previously traveled by a minimum number of client devices of the plurality of client devices.

5. The method of claim 1, wherein the plurality of previously traveled routes are received from the plurality of client devices.

6. The method of claim 3, wherein the user preference relates to popularity of previously traveled routes.

7. The method of claim 1, further comprising:

receiving a first location from the requesting client device;

selecting a second route of the plurality of routes based on the first location and the two or more locations of the given route;

stringing the given route with the second route to generate a single route, such that providing the given route includes providing the single route.

8. A method of modifying map information, the map information comprising information identifying streets, comprising:

receiving, by one or more processors, change information from each particular client device of a plurality of client devices, the change information identifying geographical locations as each particular client device'"'"'s geographical location changes over time;

storing, by the one more processors, routes traveled by each of the plurality of client devices based on the change information received from each client device;

modifying, by the one or more processors, the map information when a plurality of the stored routes do not correspond with the information identifying streets to remove a given street if the plurality of the stored routes do not correspond with the given street;

providing, by the one or more processors, one of the stored routes and the modified map information in response to a request for directions; and

updating, by the one or more processors, a database of the modified map information based on a number of the plurality of the stored routes that do not correspond with the information identifying the streets.

9. The method of claim 8, wherein modifying the map information further includes modifying the map information to identify a street corresponding with the geographical locations if the map information does not identify a street at the geographical locations.

10. The method of claim 8, wherein modifying the map information further includes modifying the map information to change a geographic location of a given street if the plurality of the stored routes do not correspond with the geographic location of the given street.

11. The method of claim 8, wherein modifying the map information further includes modifying the map information to adjust a one-way or two-way direction of a given street if the plurality of the stored routes do not correspond with a prior one-way or two-way direction of the given street identified in the map information.

12. A method comprising:

receiving, by one or more processors, a plurality of routes previously traveled by one or more client devices, each route of the plurality of routes identifying respective starting location for a particular client device and a respective ending location for that particular client device and information identifying streets;

receiving, by the one or more processors, a request for directions including a starting location and an ending location;

filtering, by the one or more processors, the plurality of routes previously traveled based on predetermined user preferences to remove undesired routes previously traveled;

selecting, by the one or more processors, a given filtered traveled route of the plurality of filtered traveled routes by comparing the respective starting locations of the filtered traveled routes to the starting location of the request and by comparing the respective ending locations of the filtered travel routes to the ending location of the request; and

filtering, by the one or more processors, the given filtered traveled route of the plurality of filtered traveled routes to remove a given street if of the plurality of filtered traveled routes do not correspond with the given street.

13. The method of claim 12, wherein the given filtered traveled route is further selected based on a number of client devices that have provided the given route.

14. The method of claim 12, wherein the given filtered traveled route is further selected based on a time that the request for directions is received.

15. The method of claim 12, wherein the given filtered traveled route is further selected by determining that the given filtered route is available by comparing the given filtered route to the plurality of routes previously traveled.

16. The method of claim 12, wherein if a route between the starting location and the ending location is unavailable,

selecting, by the one or more processors, a first previously traveled route of the plurality of routes previously traveled by comparing the respective starting locations of the plurality of routes previously traveled to the starting location of the request;

selecting, by the one or more processors, a second previously traveled route of the plurality of routes previously traveled by comparing the respective ending locations of the plurality of routes previously traveled to the ending location of the request; and

concatenating, by the one or more processors, the first previously traveled route and the second previously traveled route to generate a third route between the starting location and the ending location of the request.

17. The method of claim 12, wherein at least one of the one or more client devices comprises a component for determining a location of the client device.

18. The method of claim 17, wherein the component comprises a GPS receiver.

19. The method of claim 17 wherein the component comprises a cell phone antenna and a processor for determining the location of the client device based on signals received at the cell phone antenna.

20. The method of claim 12, wherein the given filtered traveled route is further selected based on user preferences related to popularity of the plurality of routes previously traveled.