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

• US 7,194,357 B2
• Filed: 05/26/2006
• Issued: 03/20/2007
• 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): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US11/420,682
• Publication Number:
  US 20060212218A1
• Time in Patent Office: 298 Days
• Field of Search: 701200-202, 701207-213, 340988-990, 340/995.1, 340/995.13, 340/995.16, 340/995.19, 340/995.24, 455/412.1, 455/412, 455/456.1, 455/456.3, 707 3- 4, 707/101
• US Class Current: 701/209
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• 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
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G09B 29/106 using electronic means

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 locations of interest for a route, the method comprising:

accessing shape points;

determining whether a shape point that corresponds to the route is within a predetermined distance of another shape point that corresponds to the route;

based on a determination that a shape point is within the predetermined distance of another shape point that corresponds to the route, eliminating the shape point that is within the predetermined distance of another shape point;

associating, with a remaining shape point that is among the accessed shape points that were not eliminated as being within the predetermined distance of another shape point, a spatial identifier for a portion of a grid that corresponds to the remaining shape point;

identifying locations of interest that are associated with the spatial identifier for the portion of the grid; and

identifying at least some of the identified locations of interest as locations of interest for the route.

2. The method of claim 1 wherein the predetermined distance is user-configurable.

3. The method of claim 1 wherein the predetermined distance is program-configurable and may differ based on context.

4. The method of claim 1 wherein the remaining shape point comprises a longitude and latitude coordinate of a point included in the route.

5. The method of claim 1 wherein the remaining shape point comprises an endpoint of a vector having a quantity and direction representing a shape of a portion of the route.

6. The method of claim 1 wherein the locations of interest for the route are identified by at least 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 for the route.

7. The method of claim 1 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining distances of identified locations of interest to points on the route, wherein a distance of a particular identified location to a point on the route is determined;

comparing more than one of 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.

8. The method of claim 1 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining driving distances of identified locations of interest to points on the route, wherein a driving distance of a particular identified location to a point on the route is determined;

comparing more than one of 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.

9. The method of claim 1 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining straight-line distances and driving distances of identified locations of interest to points on the route, wherein a straight-line distance and a driving distance of a particular identified location to a point on the route is determined;

comparing the determined straight-line distances and the driving distances to a threshold distance; and

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

10. The method of claim 1 wherein identifying at least some of the identified locations of interest as locations of interest for the route includes identifying all of the identified locations of interest as locations of interest for the route.

11. An apparatus for determining locations of interest for a route, the apparatus being configured to:

access shape points;

determining whether a shape point that corresponds to the route is within a predetermined distance of another shape point that corresponds to the route;

based on a determination that a shape point is within the predetermined distance of another shape point that corresponds to the route, eliminating the shape point that is within the predetermined distance of another shape point;

associate, with a remaining shape point that is among the accessed shape points that were not eliminated as being within the predetermined distance of another shape point, a spatial identifier for a portion of a grid that corresponds to the shape point;

identify locations of interest that are associated with the spatial identifier for the portion of the grid; and

identify at least some of the identified locations of interest as locations of interest for the route.

12. The apparatus of claim 11 wherein the apparatus is configured such that the predetermined distance is user-configurable.

13. The apparatus of claim 11 wherein the apparatus is configured such that the predetermined distance is program-configurable and may differ based on context.

14. The apparatus of claim 11 wherein the remaining shape point comprises a longitude and latitude coordinate of a point included in the route.

15. The apparatus of claim 11 wherein the remaining shape point comprises an endpoint of a vector having a quantity and direction representing a shape of a portion of the route.

16. The apparatus of claim 11 wherein the locations of interest for the route are identified by at least 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 for the route.

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

determine distances of identified locations of interest to points on the route, wherein a distance of a particular identified location to a point on the route is determined;

compare more than one of 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 11 wherein the apparatus is further configured to:

determine driving distances of identified locations of interest to points on the route, wherein a driving distance of a particular identified location to a point on the route is determined;

compare more than one of the driving determined 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.

19. The apparatus of claim 11 wherein the apparatus is further configured to:

determine straight-line distances and driving distances of identified locations of interest to points on the route, wherein a straight-line distance and a driving distance of a particular identified location to a point on the route is determined;

compare the determined straight-line distances and the driving distances to a threshold distance; and

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

20. An apparatus for determining locations of interest for a route, the apparatus comprising:

means for accessing shape points;

means for determining whether a shape point that corresponds to the route is within a predetermined distance of another shape point that corresponds to the route;

means for, based on a determination that a shape point is within the predetermined distance of another shape point that corresponds to the route, eliminating the shape point that is within the predetermined distance of another shape point;

means for associating, with a remaining shape point that is among the accessed shape points that were not eliminated as being within the predetermined distance of another shape point, a spatial identifier for a portion of a grid that corresponds to the shape point;

means for identifying locations of interest that are associated with the spatial identifier of the portion of the grid; and

means for identifying at least some of the identified locations of interest as locations of interest for the route.