Computing paths between geographical localities

• US 8,457,885 B2
• Filed: 06/16/2011
• Issued: 06/04/2013
• Est. Priority Date: 02/01/2011
• Status: Expired due to Fees

• Current Assignee: Boxey Tech LLC (IP Edge LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Keerthi, Arvind Vijay
• Primary Examiner(s): Marc, McDieunel
• Application Number:
  US13/498,556
• Publication Number:
  US 20120232796A1
• Time in Patent Office: 719 Days
• Field of Search: 701/428, 701/438, 701/516, 455/440, 455/443, 455/445, 379/9.02, 379/88.01, 379/88.03, 342/356, 342/357.31, 196/14.52, 196/132
• US Class Current: 701/438
• CPC Class Codes: A63F 2003/00201 Octagonal game board
• CPC Class Codes: A63F 3/00072 played along an endless track, e.g. monopoly A63F3/00069 takes precedence
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

Technology is generally described for computing paths between geographical localities. The technology can receive a request for a path between two or more geographical localities, and compute a path based at least on a popularity rating of intermediate geographical localities.

Claims

1. A method performed by a computing system having a processor and a memory device, comprising:

receiving a set of four or more identifications of geographical localities, at least one of the geographical localities generally identifiable by a name or region but not a postal street address;

receiving a set of connections between at least a subset of the set of four or more geographical localities, wherein a connection between any two geographical localities indicates a path between the two geographical localities;

identifying a popularity rating for at least a first geographical locality, wherein the popularity rating for the first geographical locality exceeds the popularity rating for a second geographical locality;

receiving a request to provide directions from the second geographical locality to a third geographical locality, the directions specified by one or more paths, each path specified as a sequence of connections;

determining by the processor that there exist at least two paths from the second geographical locality to the third geographical locality, wherein there does not exist a connection between the second and the third geographical localities, wherein a first path includes the first geographical locality but not a fourth geographical locality and a second path includes the fourth geographical locality but not the first geographical locality; and

identifying the first path as a preferable path because the popularity rating for the first geographical locality exceeds the popularity rating for the fourth geographical locality, the first path thereby comprising connections from the second geographical locality to the first geographical locality to the third geographical locality.

2. The method of claim 1 further comprising receiving a set of multiple connections between the first geographical locality and the second geographical locality.

3. The method of claim 1 further comprising receiving a set of multiple connections between the fourth geographical locality and the second geographical locality, but selecting the first geographical locality because of a popularity rating associated with the first geographical locality.

4. The method of claim 3 further comprising causing the first path to be rendered.

5. The method of claim 4 wherein the first path is rendered as a schematic diagram.

6. The method of claim 4 wherein the first path is rendered as a graph.

7. The method of claim 6 wherein the first path is rendered as a graph, wherein rendered vertices are varied in size based on their relative popularity rating.

8. The method of claim 6 wherein the first path is rendered as a graph, wherein rendered edges are varied in thickness based on their relative importance.

9. The method of claim 8 wherein a first connection is more important than a second connection if the first connection has more travel volume than the second connection.

10. The method of claim 4 wherein the rendering is more detailed near the second and the third geographical localities than near the first or the fourth geographical localities.

11. The method of claim 4 wherein the first path is rendered as a list of geographical localities.

12. The method of claim 11 further comprising rendering an item in the list corresponding to a next geographical locality differently than an item in the list corresponding to a different geographical locality.

13. The method of claim 1 wherein identifying a popularity rating for at least the first geographical locality comprises analyzing content at one or more websites.

14. The method of claim 13 wherein the popularity rating is a function of a number of web pages having content identifying one or more of the geographical localities.

15. The method of claim 13 wherein the popularity rating is a function of page ranks of web pages having content identifying one or more of the geographical localities.

16. The method of claim 1 wherein identifying a popularity rating for at least the first geographical locality comprises analyzing content at one or more social networking sites.

17. The method of claim 1 further comprising generating a graph wherein vertices of the graph represent geographical localities and edges of the graph represent the connections.

18. The method of claim 1 further comprising generating a response to the received request by employing a computational solution for solving a directed graph problem.

19. The method of claim 1 wherein at least one of the connections is one of a railway, road, bus route, or pedestrian path.

20. The method of claim 1 wherein receiving a set of connections comprises employing a connection if the connection is a relatively straight road.

21. The method of claim 1 wherein receiving a set of connections comprises employing a connection if the connection connects two geographical localities that are separated by fewer than approximately 250 meters.

22. The method of claim 1 wherein receiving a set of connections comprises employing a connection if the connection connects two geographical localities that are on a same public transit route.

23. The method of claim 1 further comprising receiving an automatically sensed present location of a user from whom the request was received.

24. The method of claim 1 wherein the popularity rating is based on a user'"'"'s indicated preference.

25. A computer-readable memory device storing instructions, the instructions comprising:

receiving a set of four or more identifications of geographical localities, at least one of the geographical localities generally identifiable by a name or region;

receiving a set of connections between at least a subset of the set of four or more geographical localities wherein the connections between any two geographical localities indicates a path between the two geographical localities;

receiving a popularity rating for at least a first and a fourth geographical localities, wherein the popularity rating for the first geographical locality exceeds the popularity rating for the fourth geographical locality;

receiving a request to provide directions from a second geographical locality to a third geographical locality;

determining that there exist at least two paths from the second geographical locality to the third geographical locality, wherein there does not exist a connection between the second and the third geographical localities, wherein a first path includes the first geographical locality and a second path includes the fourth geographical locality; and

identifying the first path as a preferable path because the popularity rating for the first geographical locality exceeds the popularity rating for the fourth geographical locality.

26. The computer-readable memory device of claim 25, further comprising instructions for:

receiving a set of multiple connections between the fourth geographical locality and the second geographical locality, but selecting the first geographical locality because of a popularity rating associated with the first geographical locality; and

causing the first path to be rendered.

27. The computer-readable memory device of claim 26, wherein the rendering is more detailed near the second and the third geographical localities than near the first or the fourth geographical localities.

28. The computer-readable memory device of claim 26, wherein the first path is rendered as a list of geographical localities.

29. The computer-readable memory device of claim 28, further comprising instructions for rendering an item in the list corresponding to a next geographical locality differently than an item in the list corresponding to a different geographical locality.

30. The computer-readable memory device of claim 25, wherein identifying a popularity rating for at least the first geographical locality comprises analyzing content at one or more websites.

31. The computer-readable memory device of claim 25, wherein identifying a popularity rating for at least the first geographical locality comprises analyzing content at one or more social networking sites.

32. The computer-readable memory device of claim 25, further comprising instructions for generating a response to the received request by employing a computational solution for solving a directed graph problem.

33. The computer-readable memory device of claim 25, wherein at least one of the connections is one of a railway, road, bus route, or pedestrian path.

34. The computer-readable memory device of claim 25, wherein receiving a set of connections comprises employing a connection if the connection is a relatively straight road.

35. The computer-readable memory device of claim 25, wherein receiving a set of connections comprises employing a connection if the connection connects two geographical localities that are separated by fewer than approximately 250 meters.

36. The computer-readable memory device of claim 25, wherein receiving a set of connections comprises employing a connection if the connection connects two geographical localities that are on a same public transit route.

37. The computer-readable memory device of claim 25, further comprising instructions for receiving an automatically sensed present location of a user from whom the request was received.

38. The computer-readable memory device of claim 25, wherein the popularity rating is based on a user'"'"'s indicated preference.

39. A system, comprising:

a component configured to receive a set of four or more identifications of geographical localities, at least one of the geographical localities generally identifiable by a name or region but not a postal address;

a component configured to receive a set of connections between at least a subset of the set of four or more geographical localities wherein the connections between any two geographical localities indicates a path between the two geographical localities;

a component configured to identify a popularity rating for at least a first geographical locality, wherein the popularity rating for the first geographical locality exceeds a popularity rating for a fourth geographical locality;

a component configured to receive a request to provide directions from a second geographical locality to a third geographical locality;

a component configured to determine that there exist at least two paths from the second geographical locality to the third geographical locality, wherein there does not exist a connection between the second and the third geographical localities, wherein a first path includes the first geographical locality but not the fourth geographical locality and a second path includes the fourth geographical locality but not the first geographical locality; and

a component configured to identify the first path as a preferable path because the popularity rating for the first geographical locality exceeds the popularity rating for the second geographical locality, the first path thereby comprising connections from the second geographical locality to the first geographical locality to the third geographical locality.

40. The system of claim 39 further comprising a component configured to receive from a user an identification of a fifth geographical locality, wherein the fifth geographical locality can be included in the preferable path.

41. The system of claim 39, further comprising:

a component configured to receive a set of multiple connections between the fourth geographical locality and the second geographical locality, and to select the first geographical locality because of a popularity rating associated with the first geographical locality; and

a component configured to cause the first path to be rendered.

42. The system of claim 41, wherein the rendering is more detailed near the second and the third geographical localities than near the first or the fourth geographical localities.

43. The system of claim 41, wherein the first path is rendered as a list of geographical localities.

44. The system of claim 43, further comprising a component configured to render an item in the list corresponding to a next geographical locality differently than an item in the list corresponding to a different geographical locality.

45. The system of claim 39, further comprising a component configured to analyze content at one or more websites.

46. The system of claim 39, further comprising a component configured to analyze content at one or more social networking sites.

47. The system of claim 39, further comprising a component configured to generate a response to the received request by employing a computational solution for solving a directed graph problem.

48. The system of claim 39, wherein at least one of the connections is one of a railway, road, bus route, or pedestrian path.

49. The system of claim 39, wherein the component configured to receive the set of connections employs a connection if the connection is a relatively straight road.

50. The system of claim 39, wherein the component configured to receive the set of connections employs a connection if the connection connects two geographical localities that are separated by fewer than approximately 260 meters.

51. The system of claim 39, wherein the component configured to receive the set of connections employs a connection if the connection connects two geographical localities that are on a same public transit route.

52. The system of claim 39, further comprising a component configured to receive an automatically sensed present location of a user from whom the request was received.

53. The system of claim 39, wherein at least one popularity rating is based on a user'"'"'s indicated preference.