Generating and using result suggest boost factors

• US 9,146,939 B1
• Filed: 09/30/2011
• Issued: 09/29/2015
• Est. Priority Date: 09/30/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhdanovich, Matsvei, Zauharodneu, Ivan
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Hershley, Mark E
• Application Number:
  US13/250,264
• Time in Patent Office: 1,460 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/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Search log data may specify map results that were provided to a user, and may further specify, for each map result, a geographic location to which the map result has been identified as relevant. For each geographic location, a number of the search results that have been identified as relevant to the geographic location may be determined, and a result suggest boost factor for the geographic location may be determined based on the number of search results that have been identified as relevant to the geographic location. A result suggest boost factor may be stored in an index, and is a value indicative of a likelihood that a query received from the user is requesting map results that are relevant to the geographic location.

Claims

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

receiving search log data for a user, the search log data specifying map results that were provided to the user, the search log data further specifying, for each map result, a geographic location to which the map result has been identified as relevant and an interaction field indicating whether the user interacted with the map result;

for each geographic location;

determining a number of the map results from the search log data that have been identified as relevant to the geographic location and with which the user interacted,

determining a result suggest boost factor for the geographic location based on the number of search results that have been identified as relevant to the geographic location and with which the user interacted, the result suggest boost factor being a value indicative of a likelihood that a query received from the user is requesting map results that are relevant to the geographic location, and

storing the result suggest boost factor in association with the user who generated the search log data;

after storing the result suggest boost factor, receiving a partially-formed query along with an identifier of the user who generated the search log data;

identifying the result suggest boost factor based on the identifier of the user received along with the query;

determining a personalized user-specific and location-specific query completion suggestion based on the partially-formed query and the result suggest boost factor, the user-specific and location-specific query completion suggestion being personalized to the user based on the search log data of that user; and

sending the personalized user-specific and location-specific query completion suggestion in response to receiving the partially-formed query.

2. The method of claim 1, wherein:

storing the result suggest boost factor in association with the user who generated the search log data comprises storing the result suggest boost factor in an index specific to the user; and

determining the result suggest boost factor for the geographic location further comprises;

receiving, from the index, neighboring result suggest boost factors for one or more neighboring geographic locations, each neighboring geographic location being within a threshold distance of the geographic location; and

determining the result suggest boost factor for the geographic location based on the neighboring result suggest boost factors.

3. The method of claim 2, wherein each of the one or more neighboring geographic locations are disjoint subdivisions of a mapped geographic region.

4. The method of claim 2, wherein each of the one or more neighboring geographic locations share a geographic location border with the geographic location.

5. The method of claim 2, wherein determining the result suggest boost factor for the geographic location further comprises:

for each of the neighboring geographic locations, determining a distance factor for the geographic location, the distance factor being inversely proportional to a distance between the geographic location and the neighboring geographic location; and

determining the result suggest boost factor for the geographic location based on the distance factors of each of the neighboring locations.

6. The method of claim 2, wherein determining the result suggest boost factor for the geographic location further comprises:

for each of the neighboring geographic locations, determining a time factor for the neighboring geographic location, the time factor being a value that is inversely proportional to an elapsed time since a most recent interaction, by the user, with a map result that references the neighboring geographic location; and

determining the result suggest boost factor for the geographic location based on the time factors of each of the neighboring locations.

7. The method of claim 1, wherein determining the personalized user-specific and location-specific query completion suggestion comprises:

receiving query data specifying one or more characters that were input into a user interface by the user;

obtaining, based on the query data, a set of candidate result suggestions, the candidate result suggestions including the one or more characters, each candidate result suggestion having a result suggest score indicative of a likelihood that the user is inputting a query that matches the candidate result suggestion; and

for each of the candidate result suggestions;

identifying a geographic location to which the candidate result suggestion has been identified as relevant;

selecting the result suggest boost factor for the identified geographic location; and

adjusting the result suggest score for the candidate result suggestion based on the selected result suggest boost factor.

8. A system, comprising:

one or more data processors; and

a memory coupled to the one or more data processors having instructions stored thereon which, when executed by the one or more data processors cause the one or more data processors to perform operations comprising;

receiving search log data for a user, the search log data specifying map results that were provided to the user, the search log data further specifying, for each map result, a geographic location to which the map result has been identified as relevant and an interaction field indicating whether the user interacted with the map result;

for each geographic location;

determining a number of the map results from the search log data that have been identified as relevant to the geographic location and with which the user interacted,

determining a result suggest boost factor for the geographic location based on the number of search results that have been identified as relevant to the geographic location and with which the user interacted, the result suggest boost factor being a value indicative of a likelihood that a query received from the user is requesting map results that are relevant to the geographic location, and

storing the result suggest boost factor in association with the user who generated the search log data;

after storing the result suggest boost factor, receiving a partially-formed query along with an identifier of the user who generated the search log data;

identifying the result suggest boost factor based on the identifier of the user received along with the query;

determining a personalized user-specific and location-specific query completion suggestion based on the partially-formed query and the result suggest boost factor, the user-specific and location-specific query completion suggestion being personalized to the user based on the search log data of that user; and

sending the personalized user-specific and location-specific query completion suggestion in response to receiving the partially-formed query.

9. The system of claim 8, wherein determining the result suggest boost factor for each geographic location further comprises:

receiving neighboring result suggest boost factors for one or more neighboring geographic locations, each neighboring geographic location being within a threshold distance of the geographic location; and

determining the result suggest boost factor for the geographic location based on the neighboring result suggest boost factors.

10. The system of claim 9, wherein each of the one or more neighboring geographic locations are disjoint subdivisions of a mapped geographic region.

11. The system of claim 9, wherein each of the one or more neighboring geographic locations share a geographic location border with the geographic location.

12. The system of claim 9, wherein determining the result suggest boost factor for each geographic location further comprises:

for each of the neighboring geographic locations, determining a distance factor for the geographic location, the distance factor being inversely proportional to a distance between the geographic location and the neighboring geographic location; and

determining the result suggest boost factor for the geographic location based on the distance factors of each of the neighboring locations.

13. The system of claim 12, wherein determining the result suggest boost factor for each geographic location based on the determined distances further comprises:

for each of the neighboring geographic locations, determining a time factor for the neighboring geographic location, the time factor being a value that is inversely proportional to an elapsed time since a most recent interaction, by the user, with a map result that references the neighboring geographic location; and

determining the result suggest boost factor for the geographic location based on the time factors of each of the neighboring locations.

14. The system of claim 9, wherein determining the personalized user-specific and location-specific query completion suggestion comprises:

receiving query data specifying one or more characters that were input into a user interface by the user;

obtaining, based on the query data, a set of candidate result suggestions, the candidate result suggestions including the one or more characters, each candidate result suggestion having a result suggest score indicative of a likelihood that the user is inputting a query that matches the candidate result suggestion; and

for each of the candidate result suggestions;

identifying a geographic location to which the candidate result suggestion has been identified as relevant;

selecting a result suggest boost factor for the identified geographic location; and

adjusting the result suggest score for the candidate result suggestion based on the selected result suggest boost factor.

15. A non-transitory computer-readable medium storing software comprising instructions executable by a processing device which, upon such execution, cause the processing device to perform operations comprising:

receiving search log data for a user, the search log data specifying map results that were provided to the user, the search log data further specifying, for each map result, a geographic location to which the map result has been identified as relevant and an interaction field indicating whether the user interacted with the map result;

for each geographic location;

determining a number of the map results from the search log data that have been identified as relevant to the geographic location and with which the user interacted,

determining a result suggest boost factor for the geographic location based on the number of search results that have been identified as relevant to the geographic location, the result suggest boost factor being a value indicative of a likelihood that a query received from the user is requesting map results that are relevant to the geographic location, and

storing the result suggest boost factor in an index associated with the user who generated the search log data;

after storing the result suggest boost factor in the index, receiving a partially-formed query along with an identifier of the user who generated the search log data;

identifying the index based on the identifier of the user;

determining a personalized user-specific and location-specific query completion suggestion based on the partially-formed query and the result suggest boost factor, the user-specific and location-specific query completion suggestion being personalized to the user based on the search log data of that user; and

sending the personalized user-specific and location-specific query completion suggestion in response to receiving the partially-formed query.

16. The computer readable medium of claim 15, wherein determining the result suggest boost factor for each geographic location further comprises:

receiving, from the index, neighboring result suggest boost factors for one or more neighboring geographic locations, each neighboring geographic location being within a threshold distance of the geographic location; and

determining the result suggest boost factor for the geographic location based on the neighboring result suggest boost factors.

17. The computer readable medium of claim 16, wherein each of the one or more neighboring geographic locations are disjoint subdivisions of a mapped geographic region.

18. The computer readable medium of claim 16, wherein each of the one or more neighboring geographic locations share a geographic location border with the geographic location.

19. The computer readable medium of claim 16, wherein determining the result suggest boost factor for each geographic location based on the determined distances further comprises:

for each of the neighboring geographic locations, determining a distance factor for the geographic location, the distance factor being inversely proportional to a distance between the geographic location and the neighboring geographic location; and

determining the result suggest boost factor for the geographic location based on the distance factors of each of the neighboring locations.

20. The computer readable medium of claim 16, wherein determining the result suggest boost factor for each geographic location further comprises:

for each of the neighboring geographic locations, determining a time factor for the neighboring geographic location, the time factor being a value that is inversely proportional to an elapsed time since a most recent interaction, by the user, with a map result that references the neighboring geographic location; and

determining the result suggest boost factor for the geographic location based on the time factors of each of the neighboring locations.

21. The computer readable medium of claim 15, wherein determining the personalized user-specific and location-specific query completion suggestion comprises:

receiving query data specifying one or more characters that were input into a user interface by the user;

obtaining, based on the query data, a set of candidate result suggestions, the candidate result suggestions including the one or more characters, each candidate result suggestion having a result suggest score indicative of a likelihood that the user is inputting a query that matches the candidate result suggestion; and

for each of the candidate result suggestions;

identifying a geographic location to which the candidate result suggestion has been identified as relevant;

selecting, from the index, a result suggest boost factor for the identified geographic location; and

adjusting the result suggest score for the candidate result suggestion based on the selected result suggest boost factor.