System and method for selecting and presenting a route to a user

• US 7,698,061 B2
• Filed: 09/23/2005
• Issued: 04/13/2010
• Est. Priority Date: 09/23/2005
• Status: Expired due to Fees

• Current Assignee: Jolly Seven, Series 70 of Allied Security Trust I (Allied Security Trust)
• Original Assignee: Scenera Technologies LLC (Scenera Research LLC)
• Inventors: Singh, Mona
• Primary Examiner(s): To, Tuan C
• Application Number:
  US11/234,464
• Publication Number:
  US 20070073480A1
• Time in Patent Office: 1,663 Days
• Field of Search: 701/200, 701/210, 701/211, 701/209, 701/214, 701/202, 701/201, 340/995, 340/995.1, 709/216, 709/213, 709/208, 709/219, 348/211.3
• US Class Current: 701/211
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G08G 1/096805 where the transmitted instructions are used to compute a route
• CPC Class Codes: G08G 1/096833 where different aspects are considered when computing the route
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

A method and system are provided for selecting and presenting a route to a user. An exemplary embodiment includes storing at least a portion of routes taken by a plurality of users; receiving from a particular user a request for at least one recommended route from an origination point to a destination point; formulating a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point and characteristics of other users of other users; retrieving a plurality of the stored routes taken by other users in response to the query; and presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

Claims

1. A method for selecting and presenting a route to a user on at least one of a server and a device, comprising:

storing on the at least one of the server and the device at least a portion of routes taken by a plurality of users;

receiving, by the at least one of the server and the device, from a particular user a request for at least one recommended route from an origination point to a destination point;

formulating, by the at least one of the server and the device, a query based on user specified parameters, including the origination point, the destination point, and characteristics of other users, to obtain routes taken by other users, wherein the characteristics of other users include demographic parameters including any combination of a name, address, sex, age, driving experience, and number of children;

retrieving, by the at least one of the server and the device, in response to the query, a plurality of the stored routes taken by other users having at least some of the characteristics of other users and related to at least one of the origination point and the destination point; and

presenting, by the at least one of the server and the device, the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

2. The method of claim 1 wherein formulating the query further comprises:

formulating the query based on route parameters, wherein the route parameters include any combination of quickness, personal safety, traffic safety, road conditions, and police activity.

3. A method for selecting and presenting a route to a user on at least one of a server and a device, comprising:

storing on the at least one of the server and the device at least a portion of routes taken by a plurality of users;

receiving, by the at least one of the server and the device, from a particular user a request for at least one recommended route from an origination point to a destination point;

formulating, by the at least one of the server and the device, a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point, and characteristics of other users;

allowing, by the at least one of the server and the device, each of the plurality of users to specify a group of users with whom the user'"'"'s routes may be shared and from whom the routes may be requested;

retrieving, by the at least one of the server and the device, a plurality of the stored routes taken by other users in response to the query; and

presenting, by the at least one of the server and the device, the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

4. The method of claim 3 wherein the specified group of users comprises a buddy list.

5. A method for selecting and presenting a route to a user on at least one of a server and a device, comprising:

storing on the at least one of the server and the device at least a portion of routes taken by a plurality of users;

receiving, by the at least one of the server and the device, from a particular user a request for at least one recommended route from an origination point to a destination point;

formulating, by the at least one of the server and the device, a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point, and characteristics of other users;

retrieving, by the at least one of the server and the device, a plurality of the stored routes taken by other users in response to the query wherein retrieving the plurality of stored routes in response to the query further comprises;

generating, by the at least one of the server and the device, one or more candidate routes from the origination point to the destination point; and

assigning, by the at least one of the server and the device, weights to the generated candidate routes based in part on how much the retrieved routes overlap the candidate routes; and

presenting, by the at least one of the server and the device, the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters by presenting at least one candidate route having the highest assigned weight to the particular user.

6. The method of claim 5 wherein the weight assigned to a particular one of the generated candidate routes is proportional to the distance at least one of the retrieved routes overlaps the particular one the generated candidate routes.

7. The method of claim 5 wherein the weight assigned to the particular one of the generated candidate routes is proportional to a number of street segments the at least one of the retrieved routes overlaps the particular one of the generated candidate routes.

8. The method of claim 5 wherein the weight assigned to the particular one of the generated candidate routes is determined by the at least one of the server and the device by:

calculating a total distance of the candidate route;

calculating a total distance that at least one segment of the at least one of the retrieved routes overlaps with a corresponding segment of the candidate route; and

assigning a value to the weight that is equal to either of the total distance of overlapping segments, or the total distance of overlapping segments divided by the total distance of the candidate route.

9. The method of claim 5 wherein presenting to the particular user the at least one recommended route further comprises:

selecting at least one of the generated candidate routes having a highest weight.

10. A system having a processor for selecting and presenting a route to a user, comprising:

a processor on at least one of a server and a device for executing a routing module;

at least one route database on the at least one of the server and the device for storing at least a portion of routes taken by at least one user;

the routing module on the at least one of the server and the device and coupled to the route database for receiving from a particular user a request for at least one recommended route from an origination point to a destination point, wherein in response to the request, the routing module is further functional for,

formulating a query based on user specified parameters, including the origination point, the destination point, and characteristics of other users, to obtain routes taken by other users, wherein the characteristics of other users include demographic parameters including any combination of a name, address, sex, age, driving experience, and number of children;

retrieving, in response to the query, from the at least one route database a plurality of the stored routes taken by one or more other users having at least some of the characteristics of other users and related to at least one of the origination point and the destination point; and

presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

11. The system of claim 10 wherein the routing module formulates the query based on route parameters that include any combination of quickness, personal safety, traffic safety, road conditions, and police activity.

12. A system having a processor for selecting and presenting a route to a user, comprising:

a processor on at least one of a server and a device for executing a routing module;

at least one route database on the at least one of the server and the device for storing at least a portion of routes taken by at least one user;

the routing module on the at least one of the server and the device and coupled to the route database for receiving from a particular user a request for at least one recommended route from an origination point to a destination point, wherein in response to the request, the routing module is further functional for,

formulating a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point, and characteristics of other users, the at least one user to specify a group of users with whom the user'"'"'s routes may be shared and from whom the routes may be requested;

retrieving from the at least one route database a plurality of the stored routes taken by one or more other users in response to the query; and

presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

13. The system of claim 12 wherein the specified group of users comprises a buddy list.

14. A system having a processor for selecting and presenting a route to a user, comprising:

a processor on at least one of a server and a device for executing a routing module;

at least one route database on the at least one of the server and the device for storing at least a portion of routes taken by at least one user;

the routing module on the at least one of the server and the device and coupled to the route database for receiving from a particular user a request for at least one recommended route from an origination point to a destination point, wherein in response to the request, the routing module is further functional for,

formulating a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point, and characteristics of other users;

retrieving from the at least one route database a plurality of the stored routes taken by one or more other users in response to the query by generating one or more candidate routes from the origination point to the destination point, and assigning weights to the generated candidate routes based in part on how much the retrieved routes overlap the candidate routes; and

presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters by presenting at least one candidate route having the highest assigned weight to the particular user.

15. The system of claim 14 wherein the weight assigned to a particular one of the generated candidate routes is proportional to the distance at least one of the retrieved routes overlaps the particular one the generated candidate routes.

16. The system of claim 14 wherein the weight assigned to the particular one of the generated candidate routes is proportional to a number of street segments the at least one of the retrieved routes overlaps the particular one of the generated candidate routes.

17. The system of claim 14 wherein the weight assigned to the particular one of the generated candidate routes is determined by the routing module on the at least one of the server and the device by:

calculating a total distance of the candidate route;

calculating a total distance that at least one segment of the at least one of the retrieved routes overlaps with a corresponding segment of the candidate route; and

assigning a value to the weight that is equal to either of the total distance of overlapping segments, or the total distance of overlapping segments divided by the total distance of the candidate route.

18. The system of claim 14 wherein the route module presents to the particular user at least one of the generated candidate routes having a highest weight.

19. A server-based method for selecting and presenting a route to a user, comprising:

storing at least a portion of routes taken by a plurality of users in a route database on a network server;

receiving, by the network server from a particular user, a request for at least one recommended route from an origination point to a destination point, wherein the request further specifies characteristics of other users;

generating, by the network server, one or more candidate routes from the origination point to the destination point;

using, by the network server, the characteristics of other users specified in the request to filter which set of users should be queried for their routes;

generating, by the network server, an origin region around the origination point, and generating a destination region around the destination point;

querying, by the network server, the route database for the routes of the filter set of users having at least a beginning segment falling within the origin region or an ending segment falling within the destination region;

assigning, by the network server, weights to the candidate routes based in part on how much the routes retrieved in response to the query overlap the candidate routes; and

selecting, by the network server, one or more of the candidate routes having a highest assigned weight and presenting the selected routes to the user.

20. A peer-to-peer method for selecting and presenting a route to a user, comprising:

locally storing at least a portion of routes taken by each of a plurality of users in respective ones of a plurality of user devices, wherein each of the user devices are capable of communicating with the other user devices over a network;

by a particular one of the user devices;

receiving a request for at least one recommended route from an origination point to a destination point, wherein the request further specifies characteristics of other users;

generating one or more candidate routes from the origination point to the destination point;

using the characteristics of other users specified in the request to filter which set of users should be queried for their routes;

querying the devices of the filter set of users for routes related to at least one of the origination point and the destination point, wherein in response, each one of the queried devices;

generates an origin region around the origination point and generates a destination region around the destination point,

retrieves the stored routes having at least a beginning segment falling within the origin region or an ending segment falling within the destination region, and

returns the retrieved routes;

assigning weights to the candidate routes based in part on how much the returned routes overlap the candidate routes; and

selecting one or more of the candidate routes having a highest assigned weight and presenting the selected routes to the user.

21. A method for selecting and presenting a route to a user on at least one of a server and a device, the method comprising:

storing a plurality of associations on the at least one of the server and the device, each association between a user having a user characteristic and a route taken by the user;

receiving, by the at least one of the server and the device, from a particular user a request, identifying an origination point and a destination point, for at least one recommended route from the origination point to the destination point;

formulating, by the at least one of the server and the device, a query based on the request and a user characteristic associated with the particular user;

retrieving, by the at least one of the server and the device, from the stored plurality of associations, in response to the query, a plurality of routes in associations between other users identified by a filter based on the user characteristic associated with the particular user; and

presenting, by the at least one of the server and the device, the at least one recommended route to the particular user including at least one of the retrieved plurality of routes determined by matching the retrieved plurality of routes with a generated candidate route from the origination point to the destination point.

22. The method of claim 21 wherein retrieving the plurality of the routes further comprises:

retrieving a plurality of routes in associations between other users having at least some characteristics of other users including the user characteristic associated with the particular user and related to at least one of the origination and destination points.

23. The method of claim 21 wherein the user characteristic associated with the particular user includes at least one demographic parameter.

24. The method of claim 23 wherein the at least one demographic parameter includes any combination of a name, address, sex, age, driving experience, and number of children.

25. The method of claim 24 wherein formulating the query further comprises:

formulating the query based on route parameters, wherein the route parameters include any combination of quickness, personal safety, traffic safety, road conditions, and police activity.

26. The method of claim 21 further comprising responding to the query by:

generating, by the at least one of the server and the device, an origin region around the origination point and generating a destination region around the destination point; and

retrieving, by the at least one of the server and the device, stored routes having at least one of a beginning segment falling within the origin region and an ending segment falling within destination region.

27. The method of claim 26 wherein responding to the query further comprises:

calculating, by the at least one of the server and the device, a radius r based on a predetermined percentage of a distance between the origination point and the destination point;

calculating, by the at least one of the server and the device, the origin region by generating a circle centered around the origination point having the radius r; and

calculating, by the at least one of the server and the device, the destination region by generating a circle centered around the destination point having the radius r.

28. The method of claim 27 wherein responding to the query further comprises:

determining, by the at least one of the server and the device, a radius R having a length less than the distance from the origination point to the destination point;

drawing, by the at least one of the server and the device, a first arc of the radius R through the origin region that is centered at the destination point;

drawing, by the at least one of the server and the device, an arc of the radius R through the destination region that is centered at the origination point; and

retrieving, by the at least one of the server and the device, saved routes that have an ending segment falling within a region bounded by the origin region and the first arc, and that have an ending segment falling with a region bounded by the destination region and the second arc.

29. The method of claim 21 wherein storing the routes further comprises:

storing the routes of each of the users locally on respective ones of a plurality of user devices.

30. The method of claim 21 wherein storing the routes further comprises:

storing route data recorded by a plurality of user devices in a route database on a network server.

31. A system having a processor for selecting and presenting a route to a user, comprising:

a processor on at least one of a server and a device for executing a routing module;

at least one route database on the at least one of the server and the device for storing a plurality of associations, each association between a user having a user characteristic and a route taken by the user;

the routing module on the at least one of the server and the device and coupled to the route database for receiving from a particular user a request, identifying an origination point and a destination point, for at least one recommended route from the origination point to the destination point, wherein in response to the request, the routing module is further functional for,

formulating a query based on the request and a user characteristic associated with the particular user;

retrieving from the at least one route database, in response to the query, a plurality of the routes in associations between other users identified by a filter based on the user characteristic associated with the particular user; and

presenting the at least one recommended route to the particular user including at least one of the retrieved routes determined by matching the retrieved routes with a generated candidate route from the origination point to the destination point.

32. The system of claim 31 wherein retrieving the plurality of the routes further comprises:

retrieving a plurality of routes taken by other users having at least some of the characteristics of other users and related to at least one of the origination and destination points.

33. The system of claim 31 wherein the user characteristic associated with the particular user includes at least one demographic parameter.

34. The system of claim 33 wherein the at least one demographic parameter includes any combination of a name, address, sex, age, driving experience, and number of children.

35. The system of claim 31 wherein the route module is further functional for the functions for:

generating an origin region around the origination point and generating a destination region around the destination point; and

retrieving stored routes from the route database having at least one of a beginning segment falling within the origin region and an ending segment falling within destination region.

36. The system of claim 35 wherein the origin region and destination region are generated by:

calculating a radius r based on a predetermined percentage of a distance between the origination point and the destination point;

calculating the origin region by generating a circle centered around the origination point having the radius r; and

calculating the destination region by generating a circle centered around the destination point having the radius r.

37. The system of claim 36 wherein the routes are further retrieved by:

determining a radius R having a length less than the distance from the origination point to the destination point;

drawing a first arc of the radius R through the origin region that is centered at the destination point;

drawing an arc of the radius R through the destination region that is centered at the origination point; and

retrieving saved routes that have an ending segment falling within a region bounded by the origin region and the first arc, and that have an ending segment falling with a region bounded by the destination region and the second arc.

38. The system of claim 31 wherein the routes of each of the users are stored locally on respective ones of a plurality of user devices.

39. The system of claim 31 wherein route data recorded by a plurality of user devices is stored in a route database on a network server.