Ranking location search results based on multiple distance measures

• US 8,898,173 B1
• Filed: 05/14/2010
• Issued: 11/25/2014
• Est. Priority Date: 05/14/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Badoiu, Mihai
• Primary Examiner(s): Fan, Shiow-Jy
• Application Number:
  US12/780,763
• Time in Patent Office: 1,656 Days
• Field of Search: 707/748, 707/E17.018, 707/E17.058
• US Class Current: 707/748
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for calculating a location relevance score for search results is disclosed. In one aspect, a location relevance score is calculated for each search result based on three distances to a physical address associated with the search result. The first distance is measured from a polygon approximating the boundary of a specified region of interest. The second distance is measured from a combined area associated with the associated zip codes of the specified region of interest. The third distance is measured from a central location determined according to criteria independent of geometry of the specified region of interest. The search results are ranked according to their associated location relevance scores.

Claims

1. A computer-implemented method performed by a data processing apparatus, comprising:

receiving, by one or more processors, a search query and a geographic region associated with the search query, the geographic region having a central location and a bounding polygon;

identifying, by the one or more processors, a plurality of candidate search results responsive to the search query, each candidate search result being associated with a geographic location;

calculating, by the one or more processors and for each candidate search result, a central distance score, wherein the central distance score comprises a score based on a first geographic distance between the geographic location of the candidate search result and the central location of the geographic region;

calculating, by the one or more processors and for each candidate search result, a polygon distance score, wherein the polygon distance score changes as a scoring function of a second geographic distance between the geographic location of the candidate search result and an edge of the bounding polygon of the geographic region nearest the geographic location of the candidate search result, wherein the scoring function uses the second geographic distance as an input and the polygon distance score is subject to a score limit;

calculating, by the one or more processors and for each candidate search result, a respective location relevance score based on the central distance score and the polygon distance score for the candidate search result; and

ranking, by the one or more processors, the plurality of candidate search results based at least in part on the calculated location relevance scores of the plurality of candidate search results.

2. The method of claim 1, wherein each of the candidate search results is associated with a zip code, and calculating the polygon distance score further comprises determining, for each candidate search result, whether the zip code for the candidate search result is included in a list of zip codes for the geographic region;

assigning a first predetermined value to the polygon distance score if the zip code is included in the list of zip codes for the geographic region and, the polygon distance score is less than the first predetermined value;

assigning a second predetermined value to the polygon distance score if the zip code is not included in the list of zip codes for the geographic region and the polygon distance score is greater than the second predetermined value.

3. The method of claim 1, wherein the polygon distance score is based on a piece-wise continuous function that is continuous across the polygon boundary, the piece-wise continuous function having a first part that increases with the second geographic distance when the geographic location is within the bounding polygon and a second part that decreases with the second geographic distance when the geographic location is outside of the bounding polygon further, comprising:

determining, for each candidate search result, whether the geographic location is within the bounding polygon; and

calculating the polygon distance score using the first part of the piece-wise continuous function if the geographic location is within the bounding polygon and using the second part of the piece-wise continuous function if the geographic location is outside of the bounding polygon.

4. The method of claim 1, further comprising:

selecting the central location based on criteria independent of geometry of the geographic region.

5. The method of claim 1, wherein the central location of the geographic region is a city center location.

6. The method of claim 1, further comprising:

for each of the candidate search results, combining the respective location relevance score for the candidate search result with another type of relevance score for the candidate search result prior to ranking the plurality of candidate search results.

7. The method of claim 1, wherein calculating a polygon distance score for candidate search results having geographic locations inside the bounding polygon of the geographic region comprises employing a function wherein:

the polygon distance score increases as a function of increasing distance between the geographic location of the candidate search result and the edge of the bounding polygon; and

the polygon distance score is subjected to a lower score limit, and

wherein calculating a polygon distance score for candidate search results having geographic locations outside the bounding polygon of the geographic region comprises employing a function wherein;

the polygon distance score decreases as a function of increasing distance between the geographic location of the candidate search result and the edge of the bounding polygon; and

the polygon distance score is subjected to an upper score limit.

8. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving a search query and a geographic region associated with the search query, the geographic region having a central location and a bounding polygon;

identifying a plurality of candidate search results responsive to the search query, each candidate search result specifying a geographic location;

calculating, for each candidate search result, a central distance score, wherein the central distance score comprises a score based on a first geographic distance between the geographic location of the candidate search result and the central location of the geographic region;

calculating, for each candidate search result, a polygon distance score, wherein the polygon distance score changes as a scoring function of a second geographic distance between the geographic location of the candidate search result and an edge of the bounding polygon of the geographic region nearest the geographic location of the candidate search result, wherein the scoring function uses the second geographic distance as an input and the polygon distance score is subject to a score limit;

calculating, for each candidate search result, a respective location relevance score based on the central distance score and the polygon distance score for the candidate search result; and

ranking the plurality of candidate search results based at least in part on the calculated location relevance scores of the plurality of candidate search results.

9. The computer storage medium of claim 8, wherein each of the candidate search results is associated with a zip code, and calculating the polygon distance score further comprises:

determining, for each candidate search result, whether the zip code for the candidate search result is included in a list of zip codes for the geographic region;

assigning a first predetermined value to the polygon distance score if the zip code is included in the list of zip codes for the geographic region and, the polygon distance score is less than the first predetermined value;

assigning a second predetermined value to the polygon distance score if the zip code is not included in the list of zip codes for the geographic region and the polygon distance score is greater than the second predetermined value.

10. The computer storage medium of claim 8, wherein the polygon distance score is based on a piece-wise continuous function that is continuous across the polygon boundary, the piece-wise continuous function having a first part that increases with the second geographic distance when the geographic location is within the bounding polygon and a second part that decreases with the second geographic distance when the geographic location is outside of the bounding polygon, and wherein the instructions cause the data processing apparatus to further perform operations comprising:

determining, for each candidate search result, whether the geographic location is within the bounding polygon; and

calculating the polygon distance score using the first part of the piece-wise continuous function if the geographic location is within the bounding polygon and using the second part of the piece-wise continuous function if the geographic location is outside of the bounding polygon.

11. The computer storage medium of claim 8, wherein the operations further comprise:

selecting the central location based on criteria independent of geometry of the geographic region.

12. The computer storage medium of claim 8, wherein the central location of the geographic region is a city center location.

13. The computer storage medium of claim 8, wherein the instructions cause the data processing apparatus to further perform operations comprising:

for each of the candidate search results, combining the location relevance score for the candidate search result with another type of relevance score for the candidate search result prior to ranking the plurality of candidate search results.

14. The computer storage medium of claim 8, wherein calculating a polygon distance score for candidate search results having geographic locations inside the bounding polygon of the geographic region comprises employing a function wherein:

the polygon distance score increases as a function of increasing distance between the geographic location of the candidate search result and the edge of the bounding polygon; and

the polygon distance score is subjected to a lower score limit, and

wherein calculating a polygon distance score for candidate search results having geographic locations outside the bounding polygon of the geographic region comprises employing a function wherein;

the polygon distance score decreases as a function of increasing distance between the geographic location of the candidate search result and the edge of the bounding polygon; and

the polygon distance score is subjected to an upper score limit.

15. A system, comprising:

one or more processors;

memory including instructions, which when executed by the one or more processors, cause the one or more processors to perform operations comprising;

receiving a search query and a geographic region associated with the search query, the geographic region having a central location and a bounding polygon;

identifying a plurality of candidate search results responsive to the search query, each candidate search result specifying a geographic location;

calculating, for each candidate search result, a central distance score, wherein the central distance score comprises a score based at least in part on a first geographic distance between the geographic location of the candidate search result and the central location of the geographic region;

calculating, for each candidate search result, a polygon distance score, wherein the polygon distance score changes as a scoring function of a second geographic distance between the geographic location of the candidate search result and an edge of the bounding polygon of the geographic region nearest the geographic location of the candidate search result, wherein the scoring function uses the second geographic distance as an input and the polygon distance score is subject to a score limit;

calculating, for each candidate search result, a respective location relevance score based on the central distance score and the polygon distance score for the candidate search result; and

ranking the plurality of candidate search results based at least in part on the calculated location relevance scores of the plurality of candidate search results.

16. The system of claim 15, wherein each of the candidate search results is associated with a zip code, and calculating the polygon distance score further comprises:

determining, for each candidate search result, whether the zip code for the candidate search result is included in a list of zip codes for the geographic region;

assigning a first predetermined value to the polygon distance score if the zip code is included in the list of zip codes for the geographic region and, the polygon distance score is less than the first predetermined value;

assigning a second predetermined value to the polygon distance score if the zip code is not included in the list of zip codes for the geographic region and the polygon distance score is greater than the second predetermined value.

17. The system of claim 15, wherein the polygon distance score is based on a piece-wise continuous function that is continuous across the polygon boundary, the piece-wise continuous function having a first part that increases with the second geographic distance when the geographic location is within the bounding polygon and a second part that decreases with the second geographic distance when the geographic location is outside of the bounding polygon, the one or more processors further performing operations comprising:

determining, for each candidate search result, whether the geographic location is within the bounding polygon; and

calculating the polygon distance score using the first part of the piece-wise continuous function if the geographic location is within the bounding polygon and using the second part of the piece-wise continuous function if the geographic location is outside of the bounding polygon.

18. The system of claim 15, wherein the operations further comprise:

selecting the central location based on criteria independent of geometry of the geographic region.

19. The system of claim 15, wherein the central location of the geographic region is a city center location.

20. The system of claim 15, wherein the one or more processors further perform operations comprising:

for each of the candidate search results, combining the location relevance score for the candidate search result with another type of relevance score for the candidate search result prior to ranking the plurality of candidate search results.

21. The system of claim 15, wherein calculating a polygon distance score for candidate search results having geographic locations inside the bounding polygon of the geographic region comprises employing a function wherein:

the polygon distance score increases as a function of increasing distance between the geographic location of the candidate search result and the edge of the bounding polygon; and

the polygon distance score is subjected to a lower score limit, and

wherein calculating a polygon distance score for candidate search results having geographic locations outside the bounding polygon of the geographic region comprises employing a function wherein;

the polygon distance score decreases as a function of increasing distance between the geographic location of the candidate search result and the edge of the bounding polygon; and

the polygon distance score is subjected to an upper score limit.