Determining the quality of locations based on travel time investment

• US 9,558,210 B1
• Filed: 03/15/2013
• Issued: 01/31/2017
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Tomkins, Andrew, Vassilvitskii, Sergei, Ravikumar, Shanmugasundaram, Mahdian, Mohammad, Pang, Bo, Raghavan, Prabhakar
• Primary Examiner(s): Badawi, Sherief
• Assistant Examiner(s): Htay, Lin Lin
• Application Number:
  US13/833,743
• Time in Patent Office: 1,418 Days
• Field of Search: 707/724
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Methods and apparatus related to associating a quality measure with a given location. For example, an anticipated distance value for a given location may be identified that is indicative of anticipated time and/or distance to reach the given location. At least one actual distance may be identified that is indicative of actual time for the one or more members to reach the given location. In some implementations, the anticipated/actual distance values may include one or more distributions. A quality measure is then determined based on a comparison of the anticipated distance value and the identified actual distance value. The quality measure is associated with the given location. The quality measure may be further based on additional factors.

Claims

1. A computer implemented method, comprising:

identifying a given location;

identifying at least one anticipated distance value for the given location, wherein the anticipated distance value is indicative of anticipated time to reach the given location and is determined based on one or both of travel times and travel distances of travel of users to other locations that share one or more characteristics with the given location;

identifying, for members in a population with indicated travel to the given location, at least one actual distance value, wherein each actual distance value is indicative of actual time for one or more of the members to reach the given location;

determining a quality measure for the given location based on a comparison of the anticipated distance value and the identified actual distance value, wherein the quality measure is determined based on a size of the difference between the anticipated distance value and the actual distance value;

associating the quality measure with the given location;

identifying an additional location;

determining an additional quality measure for the additional location;

identifying, in response to a query submitted via a computing device, a plurality of search results for the query, the search results including a first search result related to the given location and a second search result related to the additional location;

ranking the search results, including ranking the first search result and the second search result based on the quality measure and the additional quality measure; and

providing the ranked search results in response to the query.

2. The method of claim 1, further comprising:

identifying a geographic region of the given location;

identifying at least one region characteristic of the geographic region.

3. The method of claim 2, wherein the region characteristic includes a population density of the region.

4. The method of claim 2, wherein determining the quality measure for the given location is based on the region characteristic of the geographic region.

5. The method of claim 2, further comprising determining the anticipated distance value based on the region characteristic of the geographic region.

6. The method of claim 1, further comprising:

identifying one or more location characteristics of the given location;

determining the anticipated distance value for the given location based on the one or more location characteristics.

7. The method of claim 1, further comprising:

identifying one or more user characteristics; and

selecting the members of the population based on whether they share the one or more user characteristics.

8. The method of claim 7, wherein the one or more user characteristics include at least one of a semantically meaningful characteristic and a latent characteristic.

9. The method of claim 1, further comprising:

identifying a first distance value and a second distance value, wherein the first distance value is indicative of actual time for the one or more members to reach the given location from an initial location, and the second distance value is indicative of actual time for the one or more members to reach a final location from the given location; and

determining the actual distance value based on the first and second distance values.

10. The method of claim 9, wherein determining the actual distance value includes comparing the first and second distance values to an initial to final distance value, the initial to final distance value based on difference between the initial location and the final location.

11. The method of claim 9, further comprising:

identifying a third distance value for the one or more members in the population for which the first distance value and the second distance value are identified, wherein the third distance value is indicative of actual time for the one or more members to reach a second given location from the given location; and

determining the actual distance value based on the first, second, and third distance values.

12. The method of claim 11, further comprising:

identifying a second anticipated distance value for the second given location;

identifying a second location actual distance value for the second given location based on the actual distance value;

determining a quality measure for the second given location based on a comparison of the second anticipated distance value and the identified second location actual distance value;

associating the quality measure with the second given location.

13. The method of claim 1, wherein the anticipated distance value and the actual distance value are time values.

14. The method of claim 1, wherein:

the anticipated distance value includes an indication of the anticipated number of individuals that would travel an anticipated time range to reach the given location;

the actual distance value includes an indication of the actual number of the one or more members that traveled the anticipated time range to reach the given location; and

wherein determining the quality measure for the given location is based on a comparison of the anticipated number of individuals that would travel the anticipated time range to reach the given location and the actual number of the one or more members that traveled the anticipated time range to reach the given location.

15. The method of claim 1, further comprising:

identifying, for one or more of the members, a rank indicative of the number of competing locations bypassed to reach the given location; and

wherein the determining the quality measure for the given location is further based on the identified rank.

16. A system, comprising:

a non-transitory computer readable storage medium storing instructions; and

one or more processors operable to execute the instructions stored in the non-transitory computer readable storage medium, wherein execution of the instructions by the one or more processors causes the one or more processors to;

identify a given location;

identify at least one anticipated distance value for the given location, wherein the anticipated distance value is indicative of anticipated time to reach the given location and is determined based on one or both of travel times and travel distances of travel of users to other locations that share one or more characteristics with the given location;

identify, for members in a population with indicated travel to the given location, at least one actual distance value, wherein each actual distance value is indicative of actual time for one or more of the members to reach the given location;

determine a quality measure for the given location based on a comparison of the anticipated distance value and the identified actual distance value, wherein the quality measure is determined based on a size of the difference between the anticipated distance value and the actual distance value;

associate the quality measure with the given location;

identify an additional location;

determine an additional quality measure for the additional location;

identify, in response to a query submitted via a computing device, a plurality of search results for the query, the search results including a first search result related to the given location and a second search result related to the additional location;

rank the search results, including ranking the first search result and the second search result based on the quality measure and the additional quality measure; and

provide the ranked search results in response to the query.

17. The system of claim 16, wherein the instructions further include instructions to:

identify one or more location characteristics of the given location;

determine the anticipated distance value for the given location based on the one or more location characteristics.

18. The system of claim 16, wherein the instructions further include instructions to:

identify a first distance value and a second distance value, wherein the first distance value is indicative of actual time for the one or more members to reach the given location from an initial location, and the second distance value is indicative of actual time for the one or more members to reach a final location from the given location; and

determine the actual distance value based on the first and second distance values.

19. The system of claim 18, wherein the instructions to determine the actual distance value include instructions to compare the first and second distance values to an initial to final distance value, the initial to final distance value based on difference between the initial location and the final location.

20. The system of claim 18, wherein the instructions further include instructions to:

identify a third distance value for the one or more members in the population for which the first distance value and the second distance value are identified, wherein the third distance value is indicative of actual time for the one or more members to reach a second given location from the given location; and

determine the actual distance value based on the first, second, and third distance values.

21. The system of claim 16, wherein:

the anticipated distance value includes an indication of the anticipated number of individuals that would travel an anticipated time range to reach the given location;

the actual distance value includes an indication of the actual number of the one or more members that traveled the anticipated time range to reach the given location; and

wherein the instructions to determine the quality measure for the given location include instructions to determine the quality measure for the given location based on a comparison of the anticipated number of individuals that would travel the anticipated time range to reach the given location and the actual number of the one or more members that traveled the anticipated time range to reach the given location.

22. The system of claim 21, wherein the instructions further include instructions to:

identify, for one or more of the members, a rank indicative of the number of competing locations bypassed to reach the given location; and

wherein the instructions to determine the quality measure for the given location include instructions to determine the quality measure for the given location further based on the identified rank.

23. A non-transitory computer readable storage medium storing computer instructions executable by a processor to perform a method comprising:

identifying a given location;

identifying at least one anticipated distance value for the given location, wherein the anticipated distance value is indicative of anticipated time to reach the given location and is determined based on one or both of travel times and travel distances of travel of users to other locations that share one or more characteristics with the given location;

identifying, for members in a population with indicated travel to the given location, at least one actual distance value, wherein each actual distance value is indicative of actual time for one or more of the members to reach the given location;

determining a quality measure for the given location based on a comparison of the anticipated distance value and the identified actual distance value, wherein the quality measure is determined based on a size of the difference between the anticipated distance value and the actual distance value;

associating the quality measure with the given location;

identifying an additional location;

determining an additional quality measure for the additional location;

identifying, in response to a query submitted via a computing device, a plurality of search results for the query, the search results including a first search result related to the given location and a second search result related to the additional location;

ranking the search results, including ranking the first search result and the second search result based on the quality measure and the additional quality measure; and

providing the ranked search results in response to the query.