Personalized query suggestions from profile trees

• US 8,316,019 B1
• Filed: 06/23/2010
• Issued: 11/20/2012
• Est. Priority Date: 06/23/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ainslie, Alex, Li, Nan
• Primary Examiner(s): SYED, FARHAN M
• Application Number:
  US12/822,103
• Time in Patent Office: 881 Days
• Field of Search: None
• US Class Current: 707/733
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions

Abstract

Methods, systems, and apparatus, including computer program products, for personalized query suggestion are disclosed. The personalized query suggestion utilizes a personalized profile tree constructed using search history associated with a user. The personalized profile tree is a hierarchy of nodes representing categories of information that the user has previously searched or selected from search results. When a search query is received from the user, a ranked list of related queries can be generated for the received search query. Each of the related queries is compared against the nodes in the personalized profile tree, and a relevance score is given to the related query based on the depth of a matching node in the tree, and a child count for the matching node. The related queries are re-ranked based on their respective relevance scores. After the re-ranking, top-ranked related queries are presented to the user as query suggestions.

Claims

1. A computer-implemented method, comprising:

receiving a search query, the search query associated with a user identifier;

receiving a ranked list of related search queries for the received search query, the related search queries being suggested alternate queries for the search query and ranked according to a first order;

accessing a profile tree associated with the user identifier and including a hierarchy of nodes, the hierarchy of nodes including a root node and a plurality of child nodes, each child node descending from the root node or another child node, the profile tree defining a plurality of levels, each level including child nodes that descend from the root node at a same depth, and each node of the profile tree representing a respective topic that is derived from search history data associated with the user identifier, and each node of the profile tree corresponding to at least one of a term or a phrase, and wherein the terms and phrases of the profile tree correspond to the nodes of the profile tree according to the respective topics to which the search terms and phrases belong;

for each of the related search queries;

identifying, by a computer, in the profile tree one or more nodes that match the related search query;

determining, by the computer, the respective levels of the one or more nodes that match the related search query;

determining, by the computer, a respective child count for each of the one or more nodes that match the related search query, the child count for each node being proportional to a number of child nodes descending directly from the node and a number of child nodes descending indirectly from the node; and

deriving, by the computer, a respective relevance score for the related search query based on the respective levels of the one or more nodes that match the related search query and the respective child counts of the one or more nodes that match the related search query, wherein the relevance score is directly proportional to depths of the respective levels of the one or more nodes that match the related search query, and is inversely proportional to the respective child counts of the one or more nodes that match the related search query;

adjusting, by the computer, the rank of at least one of the related search queries in the list based on the respective relevance scores of the related search queries so that the search queries are ranked according to a second order different from the first order; and

providing, by the computer, suggested query data to a client device associated with the user identifier, the suggested query data operable to cause the client device to present a plurality of top-ranked related search queries according to the second order.

2. The method of claim 1, wherein the ranked list of related search queries are based on search queries previously submitted by a plurality of users.

3. The method of claim 1, wherein the search terms and phrases are search terms and phrases previously entered by a user in association with the user identifier.

4. The method of claim 3, wherein the one or more nodes that match the related search query are the nodes that explicitly correspond to at least one search term of the related search query.

5. The method of claim 1, wherein the terms and phrases are terms and phrases extracted from result documents that have been previously selected by a user during search sessions associated with the user identifier.

6. The method of claim 1, wherein for each of the related search queries, the one or more nodes that match the related search query each represents a respective topical category that includes a concept represented by terms of the related search query.

7. A non-transitory computer-readable medium having instructions stored thereon, the instructions, when executed by one or more processors, cause the one or more processors to perform operations comprising:

receiving a search query, the search query associated with a user identifier;

receiving a ranked list of related search queries for the received search query, the related search queries being suggested alternate queries for the search query and ranked according to a first order;

accessing a profile tree associated with the user identifier and including a hierarchy of nodes, the hierarchy of nodes including a root node and a plurality of child nodes, each child node descending from the root node or another child node, the profile tree defining a plurality of levels, each level including child nodes that descend from the root node at a same depth, and each node of the profile tree representing a respective topic that is derived from search history data associated with the user identifier, and each node of the profile tree corresponding to at least one of a term or a phrase, and wherein the terms and phrases of the profile tree corresponds to the nodes of the profile tree according to the respective topics to which the search terms and phrases belong;

for each of the related search queries;

identifying in the profile tree one or more nodes that match the related search query;

determining the respective levels of the one or more nodes that match the related search query;

determining a respective child count for each of the one or more nodes that match the related search query, the child count for each node being proportional to a number of child nodes descending directly from the node and a number of child nodes descending indirectly from the node; and

deriving a respective relevance score for the related search query based on the respective levels of the one or more nodes that match the related search query and the respective child counts of the one or more nodes that match the related search query, wherein the relevance score is directly proportional to depths of the respective levels of the one or more nodes that match the related search query, and is inversely proportional to the respective child counts of the one or more nodes that match the related search query;

adjusting the rank of at least one of the related search queries in the list based on the respective relevance scores of the related search queries so that the search queries are ranked according to a second order different from the first order; and

providing suggested query data to a client device associated with the user identifier, the suggested query data operable to cause the client device to present a plurality of top-ranked related search queries according to the second order.

8. The non-transitory computer-readable medium of claim 7, wherein the ranked list of related search queries are based on search queries previously submitted by a plurality of users.

9. The non-transitory computer-readable medium of claim 7, wherein the search terms and phrases are search terms and phrases previously entered by a user in association with the user identifier.

10. The non-transitory computer-readable medium of claim 9, wherein the one or more nodes that match the related search query are the nodes that explicitly correspond to at least one search term of the related search query.

11. The non-transitory computer-readable medium of claim 7, wherein the terms and phrases are terms and phrases extracted from result documents that have been previously selected by a user during search sessions associated with the user identifier.

12. The non-transitory computer-readable medium of claim 7, wherein for each of the related search queries, the one or more nodes that match the related search query each represents a respective topical category that includes a concept represented by terms of the related search query.

13. A system, comprising:

one or more processors; and

memory having instructions stored thereon, the instructions, when executed by one or more processors, comprising;

receiving a search query, the search query associated with a user identifier;

receiving a ranked list of related search queries for the received search query, the related search queries being suggested alternate queries for the search query and ranked according to a first order;

accessing a profile tree associated with the user identifier and including a hierarchy of nodes, the hierarchy of nodes including a root node and a plurality of child nodes, each child node descending from the root node or another child node, the profile tree defining a plurality of levels, each level including child nodes that descend from the root node at a same depth, and each node of the profile tree representing a respective topic that is derived from search history data associated with the user identifier, and each node of the profile tree corresponding to at least one of a term or a phrase, and wherein the terms and phrases of the profile tree correspond to the nodes of the profile tree according to the respective topics to which the search terms and phrases belong;

for each of the related search queries;

identifying in the profile tree one or more nodes that match the related search query;

determining the respective levels of the one or more nodes that match the related search query;

determining a respective child count for each of the one or more nodes that match the related search query, the child count for each node being proportional to a number of child nodes descending directly from the node and a number of child nodes descending indirectly from the node; and

deriving a respective relevance score for the related search query based on the respective levels of the one or more nodes that match the related search query and the respective child counts of the one or more nodes that match the related search query, wherein the relevance score is directly proportional to depths of the respective levels of the one or more nodes that match the related search query, and is inversely proportional to the respective child counts of the one or more nodes that match the related search query;

adjusting the rank of at least one of the related search queries in the list based on the respective relevance scores of the related search queries so that the search queries are ranked according to a second order different from the first order; and

providing suggested query data to a client device associated with the user identifier, the suggested query data operable to cause the client device to present a plurality of top-ranked related search queries according to the second order.

14. The system of claim 13, wherein the ranked list of related search queries are based on search queries previously submitted by a plurality of users.

15. The system of claim 13, wherein the search terms and phrases are search terms and phrases previously entered by a user in association with the user identifier.

16. The system of claim 15, wherein the one or more nodes that match the related search query are the nodes that explicitly corresponds to at least one search term of the related search query.

17. The system of claim 13, wherein the terms and phrases are terms and phrases extracted from result documents that have been previously selected by a user during search sessions associated with the user identifier.

18. The system of claim 13, wherein for each of the related search queries, the one or more nodes that match the related search query each represents a respective topical category that includes a concept represented by terms of the related search query.