Determining relevance scores for locations

• US 8,407,211 B1
• Filed: 12/16/2010
• Issued: 03/26/2013
• Est. Priority Date: 12/16/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lewis, Matt
• Primary Examiner(s): Vital, Pierre
• Assistant Examiner(s): Kim, Taelor
• Application Number:
  US12/969,933
• Time in Patent Office: 831 Days
• Field of Search: None
• US Class Current: 707/722
• CPC Class Codes: G06F 16/24578 using ranking
• 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, systems, and apparatus, including computer programs encoded on a computer storage medium, for determining relevance scores for locations. In one aspect, a method includes storing a respective plurality of category-location relevance scores for each location of a plurality of geographic locations. A category-location relevance score is based on a plurality of category-entity-location relevance scores for a plurality of entities associated with the category at the location. A first category-location relevance score is determined for a first geographic location that is not one of the plurality of geographic locations. Determining the first category-location relevance score includes calculating the first category-location relevance score based on a second category-location relevance score for a second geographic location in the plurality of geographic locations and a physical distance between the first geographic location and the second geographic location.

Claims

1. One or more computers comprising:

a processor;

a memory;

wherein the one or more computers are configured to perform operations comprising;

storing a respective plurality of category-location relevance scores for each location of a plurality of geographic locations, wherein each category-location relevance score for each location estimates a relevance of a respective category to the location, and wherein a category-location relevance score is based on a plurality of category-entity-location relevance scores for a plurality of entities associated with the category at the location, wherein

storing a category-location relevance score for a location comprises storing a plurality of Taylor coefficients for a function at the location, wherein an evaluation of the function for a location provides a category-location relevance score for the category, and wherein an evaluation of the function at a location is determined by evaluating a sub-function for each of the plurality of entities, and wherein an evaluation of the sub-function for an entity provides a category-entity-location relevance score for the entity and the location;

determining a first category-location relevance score for a first geographic location that is not one of the plurality of geographic locations, including;

selecting a second geographic location in the plurality of geographic locations, and

calculating the first category-location relevance score based on a second category-location relevance score for the second geographic location and a physical distance between the first geographic location and the second geographic location; and

selecting an item from a plurality of candidate items using the first category location relevance score, wherein each candidate item is associated with a respective category, and wherein selecting the item comprises;

ranking the plurality of candidate items using the first category location relevance score, and

selecting a highest ranked candidate item.

2. The system of claim 1, wherein selecting the item comprises selecting an ad from a plurality of ads for a user associated with the first geographic location.

3. The system of claim 1, wherein the category is a business category and the plurality of entities is a plurality of businesses in the business category, and wherein each category-entity-location relevance score for a business is based on a physical distance between an address of the business in the category and a geographic location.

4. The system of claim 1, wherein the first geographic location is associated with a user, and wherein the second geographic location is a prominent geographic location.

5. The system of claim 1, wherein each Taylor coefficient for the function at the location is derived from an evaluation of the function or an evaluation of the derivative of the function at the location.

6. The system of claim 1, wherein storing the plurality of Taylor coefficients comprises using automatic differentiation of the function at the location.

7. The system of claim 1, wherein approximating the first relevance score includes evaluating a Taylor series for the function using the Taylor coefficients for the function at the second geographic location and the physical distance between the first geographic location and the second geographic location.

8. A method performed by data processing apparatus, the method comprising:

one or more computers configured to perform operations comprising;

storing a respective plurality of category-location relevance scores for each location of a plurality of geographic locations, wherein each category-location relevance score for each location estimates a relevance of a respective category to the location, and wherein a category-location relevance score is based on a plurality of category-entity-location relevance scores for a plurality of entities associated with the category at the location, wherein

storing a category-location relevance score for a location comprises storing a plurality of Taylor coefficients for a function at the location, wherein an evaluation of the function for a location provides a category-location relevance score for the category, and wherein an evaluation of the function at a location is determined by evaluating a sub-function for each of the plurality of entities, and wherein an evaluation of the sub-function for an entity provides a category-entity-location relevance score for the entity and the location;

determining a first category-location relevance score for a first geographic location that is not one of the plurality of geographic locations, including;

selecting a second geographic location in the plurality of geographic locations, and

calculating the first category-location relevance score based on a second category-location relevance score for the second geographic location and a physical distance between the first geographic location and the second geographic location; and

selecting an item from a plurality of candidate items using the first category location relevance score, wherein each candidate item is associated with a respective category, and wherein selecting the item comprises;

ranking the plurality of candidate items using the first category location relevance score, and

selecting a highest ranked candidate item.

9. The method of claim 8, wherein selecting the item comprises selecting an ad from a plurality of ads for a user associated with the first geographic location.

10. The method of claim 8, wherein the category is a business category and the plurality of entities is a plurality of businesses in the business category, and wherein each category-entity-location relevance score for a business is based on a physical distance between an address of the business in the category and a geographic location.

11. The method of claim 8, wherein the first geographic location is associated with a user, and wherein the second geographic location is a prominent geographic location.

12. The method of claim 8, wherein each Taylor coefficient for the function at the location is derived from an evaluation of the function or an evaluation of the derivative of the function at the location.

13. The method of claim 8, wherein storing the plurality of Taylor coefficients comprises using automatic differentiation of the function at the location.

14. The method of claim 8, wherein approximating the first relevance score includes evaluating a Taylor series for the function using the Taylor coefficients for the function at the second geographic location and the physical distance between the first geographic location and the second geographic location.

15. 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:

storing a respective plurality of category-location relevance scores for each location of a plurality of geographic locations, wherein each category-location relevance score for each location estimates a relevance of a respective category to the location, and wherein a category-location relevance score is based on a plurality of category-entity-location relevance scores for a plurality of entities associated with the category at the location, wherein

storing a category-location relevance score for a location comprises storing a plurality of Taylor coefficients for a function at the location, wherein an evaluation of the function for a location provides a category-location relevance score for the category, and wherein an evaluation of the function at a location is determined by evaluating a sub-function for each of the plurality of entities, and wherein an evaluation of the sub-function for an entity provides a category-entity-location relevance score for the entity and the location;

determining a first category-location relevance score for a first geographic location that is not one of the plurality of geographic locations, including;

selecting a second geographic location in the plurality of geographic locations; and

calculating the first category-location relevance score based on a second category-location relevance score for the second geographic location and a physical distance between the first geographic location and the second geographic location; and

selecting an item from a plurality of candidate items using the first category location relevance score, wherein each candidate item is associated with a respective category, and wherein selecting the item comprises;

ranking the plurality of candidate items using the first category location relevance score, and

selecting a highest ranked candidate item.