Using a corridor search to identify locations of interest along a travel route

• US 7,324,896 B1
• Filed: 03/05/2007
• Issued: 01/29/2008
• Est. Priority Date: 08/04/2003
• Status: Expired due to Term

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: AOL LLC (Apollo Global Management, Inc.)
• Inventors: Smith, Marc E.
• Primary Examiner(s): Jeanglaude; Gertrude A.
• Application Number:
  US11/682,151
• Time in Patent Office: 330 Days
• Field of Search: 701200-202, 701207-213, 707 3- 4, 707/101, 340/988, 340/989, 340/990, 340/995.1, 340/995.13, 340/995.19, 340/995.24, 455/421.1, 455/457
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence

Abstract

A corridor search process is used to identify locations of interest along a travel route. The corridor search process identifies locations of interest along a travel route by using a grid search process that first identifies shape points that correspond to the travel route. Each shape point is associated with a portion of a grid system used to delineate a region of geography through which the route traverses. The portions of the grid system correspond to a corridor along the travel route. References to redundant portions of the grid system are removed, and locations of interest are identified based on an association between a location of interest with a particular portion of the grid system.

Claims

1. A method for determining a location of interest, the method comprising:

accessing data describing a hierarchy of subsections that cover a region, including;

accessing a first level in the hierarchy that is divided into one or more first subsections that cover the region,

accessing a second level in the hierarchy that is divided into two or more second subsections that also cover the region, wherein the number of second subsections used to cover the region exceed the number of first subsections used to cover the region, and

accessing at least one of the first subsections on the first level and at least one of the second subsections on the second level that cover at least partially overlapping portions of the region;

selecting one or more subsections in the hierarchy of subsections for which locations of interest are to be identified; and

identifying one or more locations of interest associated with the selected one or more subsections.

2. The method of claim 1 wherein identifying one or more locations of interest associated with the selected one or more subsections comprises identifying portions of the grid that have been redundantly identified and eliminating the redundantly identified portions of the grid such that only non-redundantly identified portions of the grid are identified as locations of interest.

3. The method of claim 1 wherein identifying one or more locations of interest associated with the selected one or more subsections comprises:

determining distances of identified locations of interest to points within the selected one or more subsections;

comparing the determined distances to a threshold distance; and

eliminating identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

4. The method of claim 3 wherein the threshold distance is user-configurable.

5. The method of claim 3 wherein the threshold distance is program-configurable and differs based on context.

6. The method of claim 1 wherein identifying one or more locations of interest associated with the selected one or more subsections comprises:

determining driving distances of identified locations of interest to points within the selected one or more subsections;

comparing the determined driving distances to a threshold driving distance; and

eliminating identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

7. The method of claim 6 wherein the threshold distance is user-configurable.

8. The method of claim 6 wherein the threshold distance is program-configurable and differs based on context.

9. The method of claim 1 further comprising:

associating, with the selected one or more subsections, a spatial identifier of a portion of the hierarchy of subsections, and wherein

identifying one or more locations of interest associated with the selected one or more subsections comprises identifying locations of interest that are associated with the spatial identifier of the portion of the hierarchy of subsections.

10. The method of claim 9 wherein each level of the hierarchy of subsections includes four quadrants.

11. The method of claim 1 wherein locations of interest are determined by an on-board vehicle navigation system.

12. The method of claim 1 further comprising displaying the identified locations of interest using a personal digital assistant.

13. The method of claim 1 further comprising displaying the identified locations of interest using an on-board navigation system.

14. The method of claim 1 wherein a location of interest is identified based on an indirect association between a location of interest and a subsection.

15. An apparatus for determining a location of interest, the apparatus being configured to:

access data describing a hierarchy of subsections that cover a region, the accessed data describing;

a first level in the hierarchy that is divided into one or more first subsections that cover the region,

a second level in the hierarchy that is divided into two or more second subsections that also cover the region, wherein the number of second subsections used to cover the region exceed the number of first subsections used to cover the region, and

wherein at least one of the first subsections on the first level and at least one of the second subsections on the second level cover at least partially overlapping portions of the region;

select one or more subsections in the hierarchy of subsections for which locations of interest are to be identified; and

identify one or more locations of interest associated with the selected one or more subsections.

16. The apparatus of claim 15 wherein the apparatus is further configured to identify portions of the grid that have been redundantly identified and eliminate the redundantly identified portions of the grid such that only non-redundantly identified portions of the grid are identified as locations of interest.

17. The apparatus of claim 15 wherein the apparatus is further configured to:

determine distances of identified locations of interest to points within the selected one or more subsections;

compare the determined distances to a threshold distance; and

eliminate identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

18. The apparatus of claim 17 wherein the threshold distance is user-configurable.

19. The apparatus of claim 17 wherein the threshold distance is program-configurable and differs based on context.

20. The apparatus of claim 15 wherein the apparatus is further configured to:

identify one or more locations of interest associated with the selected one or more subsections comprises;

determine driving distances of identified locations of interest to points within the selected one or more subsections;

compare the determined driving distances to a threshold driving distance; and

eliminate identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

21. The apparatus of claim 20 wherein the threshold distance is user-configurable.

22. The apparatus of claim 20 wherein the threshold distance is program-configurable and differs based on context.

23. The apparatus of claim 15 wherein the apparatus is further configured to:

associate, with the selected one or more subsections, a spatial identifier of a portion of the hierarchy of subsections, and wherein

identify locations of interest that are associated with the spatial identifier of the portion of the hierarchy of subsections.

24. The apparatus of claim 23 wherein each level of the hierarchy of subsections includes four quadrants.

25. The apparatus of claim 15 wherein locations of interest are determined by an on-board vehicle navigation system.

26. The method of claim 15 wherein the apparatus is further configured to display the identified locations of interest using a personal digital assistant.

27. The method of claim 15 wherein the apparatus is further configured to display the identified locations of interest using an on-board navigation system.

28. The apparatus of claim 15 wherein a location of interest is identified based on an indirect association between a location of interest and a subsection.

29. An apparatus for determining a location of interest, the apparatus comprising:

means for accessing data describing a hierarchy of subsections that cover a region, including;

means for accessing a first level in the hierarchy that is divided into one or more first subsections that cover the region,

means for accessing a second level in the hierarchy that is divided into two or more second subsections that also cover the region, wherein the number of second subsections used to cover the region exceed the number of first subsections used to cover the region, and

means for accessing at least one of the first subsections on the first level and at least one of the second subsections on the second level that cover at least partially overlapping portions of the region;

means for selecting one or more subsections in the hierarchy of subsections for which locations of interest are to be identified; and

means for identifying one or more locations of interest associated with the selected one or more subsections.