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

• US 7,054,743 B1
• Filed: 07/21/2005
• Issued: 05/30/2006
• Est. Priority Date: 08/04/2003
• Status: Expired due to Term

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: AOL Inc. (Apollo Global Management, Inc.)
• Inventors: Smith, Marc E.
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US11/185,836
• Time in Patent Office: 313 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, 4554211-412, 455/457
• 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 a location of interest, the method comprising:

accessing data describing subsections of a geographic region, the subsections dividing the geographic region independently of a route from an origin to a destination;

selecting at least one subsection that corresponds to the route from the origin to the destination by identifying data corresponding to the at least one subsection through which the route traverses; and

identifying one or more locations of interest associated with the at least one identified subsection.

2. The method of claim 1 further comprising accessing data identifying the route from the origin to the destination.

3. The method of claim 1 wherein:

a route comprises points, each point being a longitude and latitude coordinate, and

selecting at least one subsection comprises selecting at least one subsection, a selected subsection corresponding to at least one point included in the route.

4. The method of claim 1 wherein:

a route comprises endpoints of vectors, each vector having a quantity and direction representing a shape of a portion of the route, and

selecting at least one subsection comprises selecting at least one subsection, a selected subsection corresponding to at least one endpoint of a vector included in the route.

5. The method of claim 1 wherein identifying one or more locations of interest associated with the at least one identified subsections comprises:

identifying one or more subsections that have been redundantly identified,

eliminating at least one of the one or more redundantly identified subsections such that only one occurrence of an identified subsection is identified, and

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

6. The method of claim 1 further comprising identifying at least one of the identified locations of interest as a location of interest for the route.

7. The method of claim 6 wherein identifying at least one of the identified locations of interest as a location of interest for the route comprises:

determining a distance of an identified location of interest to a point along the route,

comparing the determined distance to a threshold distance, and

eliminating the identified location of interest based on the comparison of the determined distance for the identified location of interest and the threshold distance.

8. The method of claim 6 wherein identifying at least one of the identified locations of interest as a location of interest for the route comprises:

determining a driving distance of an identified location of interest to a point along the route,

comparing the determined driving distance to a threshold driving distance, and

eliminating the identified location of interest based on the comparison of the determined driving distance for the identified location of interest and the threshold driving distance.

9. The method of claim 1 wherein:

subsections of a geographic region comprise a grid that delineates a geographic region into grid portions, the grid delineating the geographic region independently of the route from the origin to the destination,

accessing data comprises accessing data describing the grid that delineates the geographic region into grid portions,

selecting at least one subsection comprises selecting at least one grid portion that corresponds to the route from the origin to the destination by identifying data corresponding to the at least one grid portion through which the route traverses, and

identifying one or more locations of interest associated with the at least one identified grid portion.

10. The method of claim 9 wherein:

the grid comprises a multiple-level grid hierarchy that includes spatial identifiers, a spatial identifier identifying a grid portion,

selecting at least one grid portion comprises selecting at least one spatial identifier that corresponds to the route from the origin to the destination by identifying a spatial identifier corresponding to a grid portion through which the route traverses, and

identifying one or more locations of interest comprises identifying one or more locations of interest associated with the at least one identified spatial identifier.

11. The method of claim 10 wherein each level of the multiple-level grid hierarchy includes four quadrants.

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

access data describing subsections of a geographic region, the subsections dividing the geographic region independently of a route from an origin to a destination,

select at least one subsection that corresponds to the route from the origin to the destination by identifying data corresponding to the at least one subsection through which the route traverses, and

identify one or more locations of interest associated with the at least one identified subsection.

13. The apparatus of claim 12 further configured to access data identifying the route from the origin to the destination.

14. The apparatus of claim 12 wherein:

a route comprises points, each point being a longitude and latitude coordinate, and

the apparatus being further configured to select at least one subsection, a selected subsection corresponding to at least one point included in the route.

15. The apparatus of claim 12 wherein:

a route comprises endpoints of vectors, each vector having a quantity and direction representing a shape of a portion of the route, and

the apparatus being further configured to select at least one subsection, a selected subsection corresponding to at least one endpoint of a vector included in the route.

16. The apparatus of claim 12 further configured to:

identify one or more subsections that have been redundantly identified,

eliminate at least one of the one or more redundantly identified subsections such that only one occurrence of an identified subsection is identified, and

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

17. The apparatus of claim 12 further configured to identify at least one of the identified locations of interest as a location of interest for the route.

18. The apparatus of claim 17 further configured to:

determine a distance of an identified location of interest to a point along the route,

compare the determined distance to a threshold distance, and

eliminate the identified location of interest based on the comparison of the determined distance for the identified location of interest and the threshold distance.

19. The apparatus of claim 17 further configured to:

determine a driving distance of an identified location of interest to a point along the route,

compare the determined driving distance to a threshold driving distance, and

eliminate the identified location of interest based on the comparison of the determined driving distance for the identified location of interest and the threshold driving distance.

20. The apparatus of claim 12 wherein:

subsections of a geographic region comprise a grid that delineates a geographic region into grid portions, the grid delineating the geographic region independently of the route from the origin to the destination, and

the apparatus being further configured to;

access data comprises accessing data describing the grid that delineates the geographic region into grid portions,

select at least one subsection comprises selecting at least one grid portion that corresponds to the route from the origin to the destination by identifying data corresponding to the at least one grid portion through which the route traverses, and

identify one or more locations of interest associated with the at least one identified grid portion.

21. The apparatus of claim 20 wherein:

the grid comprises a multiple-level grid hierarchy that includes spatial identifiers, a spatial identifier identifying a grid portion, and

the apparatus being further configured to;

select at least one grid portion comprises selecting at least one spatial identifier that corresponds to the route from the origin to the destination by identifying a spatial identifier corresponding to a grid portion through which the route traverses, and

identify one or more locations of interest comprises identifying one or more locations of interest associated with the at least one identified spatial identifier.

22. The apparatus of claim 21 wherein each level of the multiple-level grid hierarchy includes four quadrants.

23. A system for determining a location of interest, the system comprising:

means for accessing data describing subsections of a geographic region, the subsections dividing the geographic region independently of a route from an origin to a destination;

means for selecting at least one subsection that corresponds to the route from the origin to the destination by identifying data corresponding to the at least one subsection through which the route traverses; and

means for identifying one or more locations of interest associated with the at least one identified subsection.