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

• US 7,599,792 B1
• Filed: 10/31/2007
• Issued: 10/06/2009
• Est. Priority Date: 08/04/2003
• Status: Expired due to Term

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: MapQuest, Inc. (Apollo Global Management, Inc.)
• Inventors: Smith, Marc E.
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US11/932,618
• Time in Patent Office: 706 Days
• Field of Search: 701/200, 701/201, 701/208, 701/209, 340/990, 340/995.19, 340/995.24
• 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 comprising:

receiving a request for a route from a first location to a second location;

determining, based on the received request, a route from the first location to the second location;

determining an area which is spatially related to the route, and within which to identify points of interest;

identifying a first grid pattern within the area spatially related to the route, the first grid pattern encompassing a portion of the area spatially related to the route;

identifying locations of interest associated with the first grid pattern;

identifying a second grid pattern within the area spatially related to the route, the second grid pattern encompassing the first grid pattern and a broader area;

identifying locations of interest associated with the second grid pattern; and

enabling rendering of the route with at least a portion of the area spatially related to the route including one or more locations of interest identified as associated with the first or second grid patterns.

2. The method of claim 1 wherein:

identifying locations of interest associated with the first grid pattern includes searching data corresponding to locations of interest for identifiers of the first grid pattern; and

identifying locations of interest associated with the second grid pattern includes searching data corresponding to locations of interest for identifiers of the second grid pattern.

3. The method of claim 1 wherein identifying locations of interest associated with the first grid pattern comprises:

determining distances of locations of interest to one or more points within the first grid pattern;

comparing the determined distances to a threshold distance; and

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

4. The method of claim 1 wherein the first and second grid patterns each represent a different level in a hierarchy of groups of grid patterns.

5. The method of claim 4 further comprising:

associating, with the first and second grid patterns, a spatial identifier of a portion of a hierarchy of grid patterns, and wherein

identifying locations of interest associated with the first grid pattern comprises identifying locations of interest that are associated with the spatial identifier associated with the first grid pattern and identifying locations of interest associated with the second grid pattern comprises identifying locations of interest that are associated with the spatial identifier associated with the second grid pattern.

6. A method comprising:

determining a grid area to be searched for locations of interest;

identifying locations of interest associated with a first subsection, the first subsection encompassing at least a portion of the determined grid area;

identifying locations of interest associated with a second subsection, the second subsection encompassing the portion of the determined grid area and a broader grid area; and

enabling rendering of at least a portion of the determined grid area including one or more locations of interest identified as associated with the first or second subsections.

7. The method of claim 6 wherein determining a grid area to be searched for locations of interest includes determining a geographic area.

8. The method of claim 6 wherein identifying a grid area to be searched for locations of interest includes identifying a route to a destination.

9. The method of claim 6 wherein:

identifying locations of interest associated with the first subsection includes searching data corresponding to locations of interest for identifiers of the first subsection; and

identifying locations of interest associated with the second subsection includes searching data corresponding to locations of interest for identifiers of the second subsection.

10. The method of claim 6 further comprising identifying portions of the determined grid area that have been redundantly identified and eliminating the redundantly identified portions of the grid area.

11. The method of claim 6 wherein identifying locations of interest associated with the first subsection comprises:

determining distances of locations of interest to one or more points within the first subsection;

comparing the determined distances to a threshold distance; and

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

12. The method of claim 11 wherein the threshold distance is user-configurable.

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

14. The method of claim 6 wherein identifying locations of interest associated with the first subsection comprises:

determining driving distances of locations of interest to points within the first subsection;

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

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

15. The method of claim 6 wherein the first and second subsections represent different levels in a hierarchy of subsections.

16. The method of claim 15 further comprising:

associating, with the first and second subsections, a spatial identifier of a portion of a hierarchy of subsections, and wherein

identifying locations of interest associated with the first subsection comprises identifying locations of interest that are associated with the spatial identifier associated with the first subsection and identifying locations of interest associated with the second subsection includes comprises identifying locations of interest that are associated with the spatial identifier associated with the second subsection.

17. The method of claim 15 wherein each level of the hierarchy of subsections includes four quadrants.

18. The method of claim 6 further comprising rendering of the grid area using a personal digital assistant.

19. The method of claim 6 further comprising rendering of the grid area using an on-board navigation system.

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

21. An apparatus configured to:

determine a grid area to be searched for locations of interest;

identify locations of interest associated with a first subsection, the first subsection encompassing at least a portion of the determined grid area;

identify locations of interest associated with a second subsection, the second subsection encompassing the portion of the determined grid area and a broader grid area; and

enable rendering of at least a portion of the determined grid area including one or more locations of interest identified as associated with the first or second subsections.

22. The apparatus of claim 21 wherein the apparatus is further configured to identify a geographic area.

23. The apparatus of claim 21 wherein the apparatus is further configured to identify a route.

24. The apparatus of claim 21 wherein the apparatus is further configured to:

search data corresponding to locations of interest for identifiers of the first subsection; and

search data corresponding to locations of interest for identifiers of the second subsection.

25. The apparatus of claim 21 wherein the apparatus is further configured to identify portions of the determined grid area that have been redundantly identified and eliminate the redundantly identified portions of the grid area.

26. The apparatus of claim 21 wherein the apparatus is further configured to:

determine distances of locations of interest to one or more points within the first subsection;

compare the determined distances to a threshold distance; and

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

27. The apparatus of claim 26 wherein the apparatus is further configured such that the threshold distance is user-configurable.

28. The apparatus of claim 26 wherein the apparatus is further configured such that the threshold distance is program-configurable and differs based on context.

29. The apparatus of claim 28 wherein the apparatus is further configured to:

determine driving distances of locations of interest to points within the first subsection;

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

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

30. The apparatus of claim 28 wherein the apparatus is further configured such that the first and second subsections represent different levels in a hierarchy of subsections.

31. The apparatus of claim 30 wherein the apparatus is further configured to:

associate, with the first and second subsections, a spatial identifier of a portion of a hierarchy of subsections;

identify locations of interest that are associated with the spatial identifier associated with the first subsection; and

identify locations of interest that are associated with the spatial identifier associated with the second subsection.

32. The apparatus of claim 30 wherein the apparatus is further configured such that each level of the hierarchy of subsections includes four quadrants.

33. The apparatus of claim 21 wherein the apparatus is further configured to render the grid area using a personal digital assistant.

34. The apparatus of claim 21 wherein the apparatus is further configured to render the grid area using an on-board navigation system.

35. The apparatus of claim 21 wherein the apparatus is further configured such that a location of interest is identified based on an indirect association between a location of interest and a subsection.

36. An apparatus comprising:

a processor configured to determine a grid area to be searched for locations of interest;

means for identifying locations of interest associated with a first subsection, the first subsection encompassing at least a portion of the determined grid area and;

means identifying locations of interest associated with a second subsection, the second subsection encompassing the portion of the determined grid area and a broader grid area; and

a display configured to enable rendering of at least a portion of the determined grid area including one or more locations of interest identified as associated with the first or second subsections.

37. A method for enabling rendering of a route including one or more locations of interest, the method comprising:

receiving, from a user at a client, a request for a route from a first location to a second location;

determining, based on the received request, a route from the first location to the second location;

determining an area which is spatially related to the route, and within which to identify points of interest;

identifying a first grid pattern within the area spatially related to the route, the first grid pattern encompassing a portion of the area spatially related to the route;

identifying locations of interest associated with the first grid pattern;

identifying a second grid pattern within the area spatially related to the route, the second grid pattern encompassing the portion of the area spatially related to the route and a broader area;

identifying locations of interest associated with the second grid pattern; and

enabling rendering, of the route with at least a portion of the area spatially related to the route including one or more locations of interest identified as associated with the first or second grid patterns.