PROVIDING ROUTES THROUGH INFORMATION COLLECTION AND RETRIEVAL

• US 20130006517A1
• Filed: 06/28/2011
• Published: 01/03/2013
• Est. Priority Date: 06/28/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ofek, Eyal, Couckuyt, Jeffrey, Kimchi, Gur, Beckman, Brian
• Granted Patent: US 8,954,266 B2
• Time in Patent Office: Days
• US Class Current: 701/411
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• 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

Abstract

Providing directions from point A to point B may be treated as an information retrieval problem. In one example, actual routes that are traveled by people are received, and are stored in a database. When a person requests directions from point A to point B, a system searches the database to determine whether a route from A to B exists. If the route does exist, then the route may be provided as directions in response to the request. If no such route exists, then the system looks in the database for routes that have some amount of overlap with each other, and attempts to construct a route from A to B by joining known routes that overlap with each other. Rules may govern the degree of overlap that routes are to have before they can be joined.

Claims

1. A method of providing directions, the method comprising:

obtaining a plurality of routes that people have traveled by collecting Global Positioning System (GPS) data and applying said GPS data to a map;

storing said plurality of routes in a database; and

using a processor to perform acts comprising;

receiving a query that indicates a first endpoint and a second endpoint;

searching said database for one or more routes that, alone or in combination, run from said first endpoint to said second endpoint;

retrieving said one or more routes from said database;

creating a set of directions based on said one or more routes; and

providing said set of directions to a person.

2. The method of claim 1, said acts further comprising:

combining together said one or more routes to create a complete route from said first endpoint to said second endpoint, said combining being governed by a rule that specifies an amount of overlap that routes are to have in order to be combined together.

3. The method of claim 2, said rule specifying a number of legs that routes are to have in common in order to be combined together, each leg being a portion of a route with no turns.

4. The method of claim 1, said set of directions including only turns that have been taken as part of a route in said database.

5. The method of claim 1, each route in said database being associated with a cost that takes into account a time of day at which the route was traveled or a number of people in a vehicle in which the route was traveled, said acts further comprising:

choosing which of said one or more routes to use in said directions based on said cost and based on either a time of day at which said query is received or a number of people in a vehicle in which the directions will be used.

6. The method of claim 1, wherein said searching comprises:

searching for routes based on length of the routes by looking first for longer routes, and then looking for successively shorter routes.

7. The method of claim 1, wherein said searching comprises:

finding, in said database, a first route based on proximity between said first route'"'"'s starting point and said first endpoint, and based on proximity between said first route'"'"'s ending point and said second endpoint;

finding, in said database, a second route from said first endpoint to an intersection along said first route; and

finding, in said database, a third route from an intersection along said first route to said second endpoint.

8. One or more computer-readable storage media that store executable instructions to provide directions, the executable instructions, when executed by a computer, causing the computer to perform acts comprising:

receiving a query that indicates a first endpoint and a second endpoint;

retrieving a plurality of routes;

combining said plurality of routes by joining together routes that have a degree of overlap specified by a rule to create a complete route;

creating a set of directions based on said complete route; and

providing said set of directions to a person.

9. The one or more computer-readable storage media of claim 8, said routes being obtained from GPS trails of routes that have been traveled, said routes being stored in a database, wherein said retrieving retrieves said routes from said database.

10. The one or more computer-readable storage media of claim 8, said rule specifying a number of legs that routes are to have in common in order to be joined together.

11. The one or more computer-readable storage media of claim 8, wherein creating of said complete route comprises:

using, in said complete route, only turns that have been observed in routes that have been traveled.

12. The one or more computer-readable storage media of claim 8, said plurality of routes being routes obtained from GPS trails of actual routes that have been traveled, each of said plurality of routes being associated a cost, wherein said combining takes into account said cost, and wherein said cost is based on a time of day at which each route was traveled.

13. The one or more computer-readable storage media of claim 8, said plurality of routes being routes that are obtained from GPS trails of actual routes that have been traveled, each of said plurality of routes being associated a cost, wherein said combining takes into account said cost, and wherein said cost is based on a number of people who were in a vehicle when each route was traveled.

14. The one or more computer-readable storage media of claim 8, wherein said retrieving comprises:

searching for routes based on length of the routes by looking first for longer routes, and then looking for successively shorter routes.

15. A system for providing directions, the system comprising:

a Global Positioning System (GPS) trail receiver that receiving GPS trails from devices;

a route database;

a route creator that identifies, based on said GPS trails, routes that have been traveled and that stores said routes in said route database;

a memory;

a query processing component that is stored in said memory, that receives a route query comprising a first endpoint and a second endpoint, that retrieves, from said database, a plurality of overlapping routes that collectively run from said first endpoint to said second endpoint; and

a route compositor that joins said overlapping routes together based on which ones of said overlapping routes satisfy a rule governing a degree of overlap in order to create a complete route from said first endpoint to said second endpoint, wherein said query processing component provides a set of directions to a person based on said complete route.

16. The system of claim 15, wherein said rule specifies a number of legs that routes are to have in common in order to be joined.

17. The system of claim 15, wherein said route compositor includes, in said complete route, only turns that have been made in routes created from said GPS trails.

18. The system of claim 15, wherein said route compositor, in determining which routes to use in said complete route, takes into account a cost of each of said routes, said cost being based on a time of day at which said route was traveled or a number of people in a vehicle in which said route was traveled.

19. The system of claim 15, wherein said query processing component searches for said routes based on length of the routes by looking first for longer routes, and then looking for successively shorter routes.

20. The system of claim 15, wherein said query processor finds, in said database, a first route based on proximity between said first route'"'"'s starting point and said first endpoint, and based on proximity between said first route'"'"'s ending point and said second endpoint, wherein said query processor finds, in said database, a second route from said first endpoint to an intersection along said first route, and wherein said query processor finds, in said database, a third route from an intersection along said first route to said second endpoint.