Determining relevance scores for locations

• US 8,738,602 B1
• Filed: 03/25/2013
• Issued: 05/27/2014
• 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): Kim, Taelor
• Application Number:
  US13/849,628
• Time in Patent Office: 428 Days
• Field of Search: None
• US Class Current: 707/706
• 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. A system comprising:

a processor;

a memory;

one or more computers having instructions stored on non-transitory computer-readable media that when executed cause the one or more computers 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 each category-entity-location relevance score for an entity is based on a physical distance between an address of the entity and a geographic 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; and

determining a first category-location relevance score for a first geographic location that is not one of the plurality of geographic locations by 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, including 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.

2. 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 and a geographic location.

3. 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.

4. 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.

5. The system of claim 1, further comprising generating the plurality of Taylor coefficients for a location using automatic differentiation of the function at the location.

6. A method performed by data processing apparatus, the method 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; and

determining a first category-location relevance score for a first geographic location that is not one of the plurality of geographic locations by 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, including 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.

7. The method of claim 6, 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 and a geographic location.

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

9. The method of claim 6, 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.

10. The method of claim 6, further comprising generating the plurality of Taylor coefficients for a location using automatic differentiation of the function at the location.

11. 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; and

determining a first category-location relevance score for a first geographic location that is not one of the plurality of geographic locations by 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, including 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.

12. The computer storage medium of claim 11, 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 and a geographic location.

13. The computer storage medium of claim 11, wherein the first geographic location is associated with a user, and wherein the second geographic location is a prominent geographic location.

14. The computer storage medium of claim 11, 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.

15. The computer storage medium of claim 11, further comprising generating the plurality of Taylor coefficients for a location using automatic differentiation of the function at the location.