Location-based information determination

• US 20090005968A1
• Filed: 04/14/2008
• Published: 01/01/2009
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: Groupon Incorporated
• Original Assignee: Groupon Incorporated
• Inventors: Downs, Oliver B., Vengroff, Darren E.
• Granted Patent: US 7,953,548 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Techniques are described for determining and providing location-based information, including based on decomposing a geographic area into numerous smaller areas and using one or more layers of polygons to represent various of the smaller areas. In some situations, location-based information for a geographic area is determined efficiently and accurately to reflect actual travel distances and/or times, such as for use in identifying one or more points of interest that are sufficiently proximate to an indicated location (e.g., a current location of a user), and/or to determine actual travel distances and/or times between two or more indicated locations of interest. The location-based information determination may in some situations be performed in a realtime or near-realtime manner after a request is received from a user, such as to interactively provide results to the user that include or are based at least in part on the determined location-based information.

Claims

1. A method for a computing system to determine location-related information for points of interest, the method comprising:

obtaining map information for a geographic area of interest;

determining polygon-based information for the geographic area that represents actual travel distances in the geographic area by,

decomposing the geographic area into a plurality of smaller areas based at least in part on the obtained map information, the smaller areas represented with a first polygon layer that includes a plurality of non-overlapping adjacent polygons of substantially similar size, and determining an associated approximate actual travel distance in the geographic area that the polygons of the first polygon layer each represent based on an average diameter of the polygons of the first polygon layer; and

automatically generating a hierarchy of polygon layers that includes the first polygon layer as a lowest level of the hierarchy and that includes one or more additional polygon layers for the geographic area that are successively higher in the hierarchy, each of the additional polygon layers including successively larger polygons that each include multiple polygons from a next lower polygon layer in the hierarchy, and associating an approximate actual travel distance with each of the polygons of the additional polygon layers based on the approximate actual travel distances of at least some of the multiple polygons from the next lower polygon layer that are included in the polygon; and

for each of multiple search requests for points of interest in the geographic area that are within an indicated distance from an indicated origination point,

automatically using the hierarchy of polygon layers to identify a search area for the search request that approximates a subset of the geographic area within the indicated distance of the indicated origination point, the identified search area being one or more polygons from at least one of the polygon layers of the hierarchy that are selected based at least in part on the approximate actual travel distances associated with the selected one or more polygons; and

providing search results for the search request by identifying points of interest that are present in the one or more selected polygons.

2. The method of claim 1 wherein the using of the hierarchy of polygon layers for a search request includes:

determining a polygon of the first polygon layer that includes the origination point for the search request;

determining a lowest polygon layer in the hierarchy that has a single polygon that includes the determined first polygon layer polygon and that has an associated approximate actual travel distance of at least the indicated distance for the search request; and

selecting the single polygon of the determined lowest polygon layer as the one or more polygons that are the identified search area for the search request, such that the identified points of interest are present in the selected single polygon.

3. The method of claim 1 wherein the obtained map information includes information about travel routes in the geographic area over which an indicated type of travel is possible, and wherein the determining of the polygon-based information that represents actual travel distances in the geographic area is based at least in part on the travel routes information, such that the one or more polygons selected for the identified search area for a search request have associated approximate actual travel distances that are based on the travel routes information.

4. The method of claim 3 wherein the decomposing of the geographic area into the plurality of smaller areas includes automatically generating the plurality of polygons of the first polygon layer and determining travel connectivity information for the polygons of the first polygon layer based at least in part on the travel routes information, the travel connectivity for the polygons of the first polygon layer indicating whether travel of the indicated type is possible between each pair of adjacent polygons of the first polygon layer so as to allow travel of the indicated type to pass directly from one of the polygons of the pair to the other polygon of the pair, and wherein the automatic generating of the hierarchy of polygon layers includes automatically generating the successively larger polygons of each additional polygon layer based at least in part on the determined travel connectivity information for the polygons of the first polygon layer, such that each of the successively larger polygons of the additional polygon layers does not include a pair of polygons of the next lower polygon layer if travel of the indicated type is not possible between that pair of polygons.

5. A computer-implemented method for determining location-related information for points of interest, the method comprising:

determining information about subareas of a geographic area, the subareas represented using a hierarchy of polygon layers, the hierarchy including a lowest first polygon layer with a plurality of non-overlapping adjacent polygons, the hierarchy further including one or more successively higher additional polygon layers that each have a plurality of polygons larger than the polygons of a next lower polygon layer of the hierarchy, the polygons of the additional polygon layers each including multiple polygons from the next lower polygon layer;

associating an approximate average distance in the geographic area with each of the polygons of the first polygon layer based on an average size of the polygon, and associating an approximate average distance in the geographic area with each of the polygons of the additional polygon layers based on the approximate average distances of at least some of the multiple polygons from the next lower polygon layer that are included in the polygon;

automatically determining information about distance in the geographic area based on the hierarchy of polygon layers, by;

determining one or more polygons of one or more polygon layers of the hierarchy that include at least one of first and second points of interest; and

determining an approximate actual distance between the first and second points based at least in part on the average distances associated with the determined polygons; and

providing an indication of the determined approximate actual distance to reflect actual travel between the first and second points.

6. The method of claim 5 wherein the automatic determining of the information about distance in the geographic area is performed in response to a request for search results within an indicated distance of a starting point of interest, the starting point being the first point of interest, wherein the determined one or more polygons include the first point of interest, wherein the method further comprises identifying the requested search results based on one or more points of interest identified within one or more subareas of the geographic area to which the determined one or more polygons correspond, the one or more identified points of interest including the second point of interest, and wherein the providing of the indication of the determined approximate actual distance includes providing information about the search results that includes the determined approximate actual distance between the first and second points.

7. The method of claim 6 wherein the determined one or more polygons are a single polygon of one of the polygon layers that includes the starting point of interest and that has an associated average distance that exceeds the indicated distance, and wherein the determined approximate actual distance between the first and second points is based at least in part on the associated average distance of the single polygon.

8. The method of claim 6 wherein the determined one or more polygons are at a highest of the polygon layers having a single polygon that includes the starting point of interest and that has an associated average distance smaller than the indicated distance, the determined one or more polygons being the single polygon, and wherein the determined approximate actual distance between the first and second points is based at least in part on the associated average distance of the single polygon.

9. The method of claim 6 wherein the determined one or more polygons include multiple polygons such that one of the multiple polygons includes the starting point of interest and such that another of the multiple polygons includes the second point of interest, and wherein the determined approximate actual distance between the first and second points is based at least in part on a combination of the associated average distances for at least some of the multiple polygons, the at least some polygons including the one polygon and the another polygon.

10. The method of claim 5 wherein the automatic determining of the information about distance in the geographic area is performed in response to a request for information about travel distance from a starting point of interest to a destination point of interest, the starting point of interest being the first point of interest and the destination point of interest being the second point of interest, wherein the determined one or more polygons are a single polygon of one of the polygon layers that includes the starting point of interest and that includes the destination point of interest, and wherein the determined approximate actual distance between the first and second points is based at least in part on the associated average distance of the single polygon.

11. The method of claim 5 wherein the automatic determining of the information about distance in the geographic area is performed in response to a request for information about travel distance from a starting point of interest to a destination point of interest, the starting point of interest being the first point of interest and the destination point of interest being the second point of interest, wherein the determined one or more polygons include multiple polygons that represent a route from the starting point of interest to the destination point of interest such that one of the multiple polygons includes the starting point of interest and such that another of the multiple polygons includes the destination point of interest, and wherein the determined approximate actual distance between the first and second points is based at least in part on a combination of the associated average distances for at least some of the multiple polygons, the at least some polygons including the one polygon and the another polygon

12. The method of claim 5 wherein the determining of the information about the subareas includes automatically generating the polygons of the additional polygon layers, and wherein the associating of the approximate average distance with each of the polygons of the additional polygon layers is performed automatically.

13. The method of claim 12 wherein the determining of the information about the subareas further includes automatically generating the polygons of the first polygon layer, and wherein the associating of the approximate average distance with each of the polygons of the first polygon layer is performed automatically.

14. The method of claim 5 wherein the polygons of the first polygon layer are at least one of a substantially similar size and of a substantially similar shape.

15. The method of claim 5 wherein the polygons of the first polygon layer are constructed such that the associated average distances for the polygons of the first polygon layer are substantially equal.

16. The method of claim 5 wherein the polygons of the first polygon layer are constructed so as to represent existing travel routes in the geographic area using one or more types of travel, such that the determined approximate actual distance to reflect actual travel between the first and second points is based on travel of at least one of the one or more travel types.

17. The method of claim 5 further comprising associating travel connectivity information with each of at least some of the polygons of the first polygon layer, the travel connectivity information representing whether direct travel of an indicated type is possible between at least some pairs of adjacent polygons of the first polygon layer, and wherein the polygons of one or more of the additional polygon layers are constructed so as to reflect the travel connectivity information associated with the at least some polygons of the first polygon layer, such that the determined approximate actual distance between the first and second points is based at least in part on the travel connectivity information associated with the at least some polygons of the first polygon layer.

18. The method of claim 5 wherein the determining of the information about the subareas and the automatic determining of the information about distance is the geographic area are performed in response to a request for the determined information about the distance.

19. The method of claim 5 wherein the determining of the information about the subareas and the associating of the approximate average distance in the geographic area for each of the polygons of the first polygon layer and of the additional polygon layers is performed prior to a request for determined information about the distance, and wherein the automatically determining of the information about distance in the geographic area and the providing of the indication of the determined approximate actual distance are performed in response to each of multiple requests.

20. The method of claim 5 wherein each of the polygons of the first polygon layer represents a distinct subarea of the geographic area, wherein each of the polygons of the additional polygon layers represents a larger subarea of the geographic area than the polygons of the next lower polygon layer of the hierarchy, and wherein the average distances associated with each of the polygons represent an actual travel distance through the subarea that the polygon represents, such that the indicated determined approximate actual distance between the first and second points represents an approximate distance of actual travel between the first and second points.

21. The method of claim 20 wherein the determining of the approximate actual distance between the first and second points further includes determining an approximate actual travel time for travel between the first and second points based at least in part on the hierarchy of polygon layers, and wherein the providing of the indication of the determined approximate actual distance includes providing an indication of the determined approximate actual travel time.

22. The method of claim 21 wherein the determining of the approximate actual travel time for travel between the first and second points is further based on information about one or more current conditions that affect travel in the geographic area.

23. A computer-readable medium whose contents enable a computing device to determine location-related information of interest, by performing a method comprising:

obtaining information about a geographic area, the obtained information including at least a first polygon layer with a plurality of polygons such that each of the polygons represents a subarea of the geographic area, each of the polygons of the first polygon layer having an associated value for a measurement of travel through the subarea that corresponds to the polygon;

automatically determining approximate travel information for the geographic area based on the plurality of polygons, by;

determining one or more of the polygons that include at least one of multiple locations of interest; and

determining an approximate value of a measurement of travel between at least two of the multiple locations based at least in part on the associated travel measurement values for at least one of the determined polygons; and

providing an indication of the determined approximate travel measurement value to reflect approximate actual travel between the at least two locations.

24. The computer-readable medium of claim 23 wherein the polygons of the first polygon layer are non-overlapping and adjacent so as to represent a plurality of subareas of the geographic area, wherein the obtained information further includes a hierarchy of multiple polygon layers that include the first polygon layer as a lowest polygon layer of the hierarchy and further include one or more successively higher additional polygon layers that each have a plurality of polygons larger than the polygons of a next lower polygon layer of the hierarchy, the polygons of the additional polygon layers each including multiple polygons from the next lower polygon layer, wherein the measurement of travel is an approximate actual average travel distance such that each of the polygons of the first polygon layer has an associated approximate actual average travel distance for the geographic area that is based on an average size of the polygon and such that each of the polygons of the additional polygon layers has an associated approximate average travel distance based on the approximate average travel distances of at least some of the multiple polygons from the next lower polygon layer that are included in the polygon, and wherein the determined approximate travel measurement value is a determined approximate actual travel distance between the at least two locations.

25. The computer-readable medium of claim 24 wherein the at least two of the multiple locations include a first location of a first point of interest and a second location of a second point of interest, wherein the at least one of the multiple locations of interest include at least one of the first and second locations, and wherein the automatic determining of the approximate travel information for the geographic area includes automatically determining information about approximate actual travel distance in the geographic area based on the hierarchy of polygon layers, such that the determining of the one or more polygons that include the at least one of multiple locations of interest includes determining one or more polygons of one or more polygon layers of the hierarchy that include at least one of the first and second points of interest.

26. The computer-readable medium of claim 23 wherein the obtained information further includes a hierarchy of multiple polygon layers that include the first polygon layer as a lowest polygon layer of the hierarchy and further include one or more successively higher additional polygon layers that each have a plurality of polygons larger than the polygons of a next lower polygon layer of the hierarchy so as to each represent a larger subarea of the geographic area than the polygons of the next lower polygon layer of the hierarchy.

27. The computer-readable medium of claim 26 wherein the measurement of travel is travel distance such that each of the polygons of the first and additional polygon layers has an associated travel distance for the subarea of the geographic area that the polygon represents, wherein the automatic determining of the approximate travel information for the geographic area is performed in response to a request for search results within an indicated distance of a starting location of interest, wherein the determined one or more polygons are a single polygon of one of the polygon layers that includes the starting location of interest and that has an associated travel distance that corresponds to the indicated distance, wherein the method further comprises identifying the requested search results at one or more other locations of interest within that subarea of the geographic area that the single polygon represents, wherein the determining of the approximate value of the measurement of travel between at least two of the multiple locations includes, for each of at least one of the one or more other locations of interest, determining an approximate travel distance from the starting location of interest to the other location of interest, and wherein the providing of the indication of the determined approximate travel measurement value includes providing information about the search results that includes an identification of the at least one other locations of interest and of the determined approximate travel distance for each of the at least one other locations of interest.

28. The computer-readable medium of claim 26 wherein the measurement of travel is travel time such that each of the polygons of the first and additional polygon layers has an associated travel time for the subarea of the geographic area that the polygon represents, wherein the automatic determining of the approximate travel information for the geographic area is performed in response to a request for search results within an indicated travel time of a starting location of interest, wherein the determined one or more polygons are a single polygon of one of the polygon layers that includes the starting location of interest and that has an associated travel time that corresponds to the indicated travel time, wherein the method further comprises identifying the requested search results at one or more other locations of interest within the subarea of the geographic area that the single polygon represents, wherein the determining of the approximate value of the measurement of travel between at least two of the multiple locations includes, for each of at least one of the one or more other locations of interest, determining an approximate travel time from the starting location of interest to the other location of interest, and wherein the providing of the indication of the determined approximate travel measurement value includes providing information about the search results that includes an identification of the at least one other locations of interest and of the determined approximate travel time for each of the at least one other locations of interest.

29. The computer-readable medium of claim 26 wherein the measurement of travel is travel time such that each of the polygons of the first and additional polygon layers has an associated travel time for the subarea of the geographic area that the polygon represents, wherein the automatic determining of the approximate travel information for the geographic area is performed in response to a request for information about travel time from a starting location of interest to a destination location of interest, wherein the determined one or more polygons are a single polygon of one of the polygon layers that includes the starting location of interest and that includes the destination location of interest, wherein the determining of the approximate value of the measurement of travel between at least two of the multiple locations includes determining an approximate travel time from the starting location of interest to the destination location of interest based on the associated travel time for the single polygon, and wherein the providing of the indication of the determined approximate travel measurement value includes providing information about the determined approximate travel time.

30. The computer-readable medium of claim 23 wherein the measurement of travel is travel time such that each of the polygons of the first polygon layer has an associated travel time for the subarea of the geographic area that the polygon represents, wherein the automatic determining of the approximate travel information for the geographic area is performed in response to a request for information about travel time from a starting location of interest to a destination location of interest, wherein the determined one or more polygons include a sequence of multiple connecting polygons from a first polygon that includes the starting location of interest to a last polygon that includes the destination location of interest, wherein the determining of the approximate value of the measurement of travel between at least two of the multiple locations includes determining an approximate travel time from the starting location of interest to the destination location of interest based at least in part on the associated travel times for the multiple polygons of the sequence, and wherein the providing of the indication of the determined approximate travel measurement value includes providing information about the determined approximate travel time.

31. The computer-readable medium of claim 23 wherein the plurality of polygons are constructed such that the associated travel measurement values for the polygons are substantially equal.

32. The computer-readable medium of claim 23 wherein the computer-readable medium is at least one of a memory of a computing device and a data transmission medium transmitting a generated data signal containing the contents.

33. The computer-readable medium of claim 23 wherein the contents are instructions that when executed cause the computing device to perform the method.

34. The computer-readable medium of claim 23 wherein the contents include one or more data structures for use in determining the location-related information of interest, the data structures comprising multiple entries, each entry corresponding to one of multiple polygon layers of a hierarchy and containing information about a plurality of polygons of the polygon layer that each represent a distinct subarea of the geographic area.

35. A computing system configured to determine location-related information of interest, comprising:

one or more memories; and

a location-based information provider system that is configured to determine location-related information of interest, by;

obtaining information about a plurality of polygons that each represent a distinct subarea of a geographic area, the plurality of polygons being part of a hierarchy of polygon layers that includes a lowest first polygon layer with multiple of the plurality of polygons and that further includes one or more successively higher additional polygon layers that each have multiple of the plurality of polygons that are larger than the polygons of a next lower polygon layer of the hierarchy, the polygons of the additional polygon layers each including one or more polygons from the next lower polygon layer, each of the polygons of the first polygon layer having an associated average distance to reflect actual travel of one or more travel types through the subarea that the polygon represents, and each of the polygons of the additional polygon layers having an associated average distance based at least in part on the average distances of at least some of the one or more polygons from the next lower polygon layer that are included in the polygon;

determining one or more polygons of one or more polygon layers of the hierarchy that include at least one of multiple locations of interest;

determining an actual distance between at least two of the multiple locations based at least in part on the average distances associated with the determined polygons; and

providing an indication of the determined actual distance to reflect actual travel between the at least two locations.

36. The computing system of claim 35 wherein the location-based information provider system includes software instructions for execution in memory of the computing system.

37. The computing system of claim 35 wherein the location-based information provider system consists of a means for determining location-related information of interest, by:

obtaining information about a plurality of polygons that each represent a distinct subarea of a geographic area, the plurality of polygons being part of a hierarchy of polygon layers that includes a lowest first polygon layer with multiple of the plurality of polygons and that further includes one or more successively higher additional polygon layers that each have multiple of the plurality of polygons that are larger than the polygons of a next lower polygon layer of the hierarchy, the polygons of the additional polygon layers each including one or more polygons from the next lower polygon layer, each of the polygons of the first polygon layer having an associated average distance to reflect actual travel of one or more travel types through the subarea that the polygon represents, and each of the polygons of the additional polygon layers having an associated average distance based at least in part on the average distances of at least some of the one or more polygons from the next lower polygon layer that are included in the polygon;

determining one or more polygons of one or more polygon layers of the hierarchy that include at least one of multiple locations of interest;

determining an actual distance between at least two of the multiple locations based at least in part on the average distances associated with the determined polygons; and

providing an indication of the determined actual distance to reflect actual travel between the at least two locations.