Personalized term importance evaluation in queries

• US 8,326,861 B1
• Filed: 06/23/2010
• Issued: 12/04/2012
• Est. Priority Date: 06/23/2010
• Status: Expired due to Fees

• 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,114
• Time in Patent Office: 895 Days
• Field of Search: None
• US Class Current: 707/768
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536

Abstract

Methods, systems, and apparatus, including computer program products, for personalized term importance evaluation in natural language queries are disclosed. The personalized term importance evaluation 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, each term and phrase in the search query is compared against the nodes in the personalized profile tree, and an importance score is given to the search term or phrase based on the depth of a matching node in the tree, and a child count for the matching node. An alternative query can be generated from a subset of the search terms that have respective importance scores exceeding a predetermined threshold.

Claims

1. A computer-implemented method, comprising:

receiving a search query, the search query comprising a sequence of search terms and associated with a user identifier;

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 terms and phrases belong;

for each of the search terms;

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

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

determining a respective child count for each of the one or more nodes that match the search term, 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

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

identifying search terms in the search query that have respective importance scores exceeding a threshold; and

generating an alternative query from the identified search terms that have respective importance scores that exceed the threshold.

2. The method of claim 1, further comprising:

removing one or more stop words from the search query to produce the sequence of search terms.

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:

for each of the sequence of search terms in the search query, the one or more nodes that match the search term explicitly correspond to the search term.

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

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

7. The method of claim 1, further comprising:

generating a plurality of search phrases from the sequence of search terms, each search phrase including two or more consecutive search terms;

for each of the search phrases;

identifying in the profile tree one or more nodes corresponding to phrases that match the search phrase;

determining the respective levels of the one or more nodes corresponding to phrases that match the search phrase;

determining respective counts of child nodes for the one or more nodes corresponding to phrases that match the search phrase; and

determining a respective importance score for the search phrase based on the respective levels and the respective counts of child nodes for the one or more nodes corresponding to phrases that match the search phrase;

identifying search phrases in the search query that have respective importance scores exceeding the threshold; and

generating the alternative query from both the identified search terms and the identified search phrases that have respective importance scores exceeding the threshold.

8. The method of claim 1, further comprising:

prior to accessing the profile tree and generating the alternative query;

performing a first search using the search query to identify a first plurality of result documents responsive to the search query;

determining quality of the first plurality of result documents;

proceeding to accessing the profile tree and generating the alternative query if the quality of the first plurality of result documents does not satisfy a pre-determined quality criterion; and

providing first search result data to a client device associated with the user identifier if the quality of the first plurality of result document satisfy the pre-determined quality criterion, the first search result data operable for causing the client device to present a first result listing comprising the first plurality of result documents.

9. The method of claim 8, further comprising:

performing a second search using the alternative query to identify a second plurality of result documents responsive to the alternative query; and

providing second search result data to the client device associated with the user identifier, the second search result data operable for causing the client device to present a second result listing comprising the second plurality of result documents.

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

receiving a search query, the search query comprising a sequence of search terms and associated with a user identifier;

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 terms and phrases belong;

for each of the search terms;

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

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

determining a respective child count for each of the one or more nodes that match the search term, 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

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

identifying search terms in the search query that have respective importance scores exceeding a threshold; and

generating an alternative query from the identified search terms that have respective importance scores that exceed the threshold.

11. The computer-readable medium of claim 10, wherein the operations further comprise:

removing one or more stop words from the search query to produce the sequence of search terms.

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

13. The computer-readable medium of claim 12, wherein:

for each of the sequence of search terms in the search query, the one or more nodes that match the search term explicitly correspond to the search term.

14. The computer-readable medium of claim 10, wherein the search terms and phrases are terms and phrases extracted from result documents that have been previously selected by a user in association with the user identifier.

15. The computer-readable medium of claim 10, wherein for each of the sequence of search terms in the search query, the one or more nodes that match the search term each represents a respective topical category that includes a concept represented by the search term.

16. The computer-readable medium of claim 10, wherein the operations further comprise:

generating a plurality of search phrases from the sequence of search terms, each search phrase including two or more consecutive search terms;

for each of the search phrases;

identifying in the profile tree one or more nodes corresponding to phrases that match the search phrase;

determining the respective levels of the one or more nodes corresponding to phrases that match the search phrase;

determining respective counts of child nodes for the one or more nodes corresponding to phrases that match the search phrase; and

determining a respective importance score for the search phrase based on the respective levels and the respective counts of child nodes for the one or more nodes that match the search phrase;

identifying search phrases in the search query that have respective importance scores exceeding the threshold; and

generating the alternative query from both the identified search terms and the identified search phrases that have respective importance scores exceeding the threshold.

17. The computer-readable medium of claim 10, wherein the operations further comprise:

prior to accessing the profile tree and generating the alternative query;

performing a first search using the search query to identify a first plurality of result documents responsive to the search query;

determining quality of the first plurality of result documents;

proceeding to accessing the profile tree and generating the alternative query if the quality of the first plurality of result documents does not satisfy a pre-determined quality criterion; and

providing first search result data to a client device associated with the user identifier if the quality of the first plurality of result document satisfy the pre-determined quality criterion, the first search result data operable for causing the client device to present a first result listing comprising the first plurality of result documents.

18. The computer-readable medium of claim 17, wherein the operations further comprise:

performing a second search using the alternative query to identify a second plurality of result documents responsive to the alternative query; and

providing second search result data to the client device associated with the user identifier, the second search result data operable for causing the client device to present a second result listing comprising the second plurality of result documents.

19. A system, comprising:

one or more processors; and

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

receiving a search query, the search query comprising a sequence of search terms and associated with a user identifier;

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 terms and phrases belong;

for each of the search terms;

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

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

determining a respective child count for each of the one or more nodes that match the search term, 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

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

identifying search terms in the search query that have respective importance scores exceeding a threshold; and

generating an alternative query from the identified search terms that have respective importance scores that exceed the threshold.

20. The system of claim 19, wherein the operations further comprise:

removing one or more stop words from the search query to produce the sequence of search terms.

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

22. The system of claim 21, wherein:

for each of the sequence of search terms in the search query, the one or more nodes that match the search term explicitly correspond to the search term.

23. The system of claim 19, wherein the search terms and phrases are terms and phrases extracted from result documents that have been previously selected by a user in association with the user identifier, and the terms and phrases included in the profile tree are distributed among the nodes in the profile tree according to the respective topics to which the terms and phrases belong.

24. The system of claim 19, wherein for each of the sequence of search terms in the search query, the one or more nodes that match the search term each represents a respective topical category that includes a concept represented by the search term.

25. The system of claim 19, wherein the operations further comprising:

generating a plurality of search phrases from the sequence of search terms, each search phrase including two or more consecutive search terms;

for each of the search phrases;

identifying in the profile tree one or more nodes corresponding to the phrases that match the search phrase;

determining the respective levels of the one or more nodes corresponding to the phrases that match the search phrase;

determining respective counts of child nodes for the one or more nodes corresponding to the phrases that match the search phrase; and

determining a respective importance score for the search phrase based on the respective levels and the respective counts of child nodes for the one or more nodes that match the search phrase;

identifying search phrases in the search query that have respective importance scores exceeding the threshold; and

generating the alternative query from both the identified search terms and the identified search phrases that have respective importance scores exceeding the threshold.

26. The system of claim 19, wherein the operations further comprise:

prior to accessing the profile tree and generating the alternative query;

performing a first search using the search query to identify a first plurality of result documents responsive to the search query;

determining quality of the first plurality of result documents;

proceeding to accessing the profile tree and generating the alternative query if the quality of the first plurality of result documents does not satisfy a pre-determined quality criterion; and

providing first search result data to a client device associated with the user identifier if the quality of the first plurality of result document satisfy the pre-determined quality criterion, the first search result data operable for causing the client device to present a first result listing comprising the first plurality of result documents.

27. The system of claim 26, wherein the operations further comprise:

performing a second search using the alternative query to identify a second plurality of result documents responsive to the alternative query; and

providing second search result data to the client device associated with the user identifier, the second search result data operable for causing the client device to present a second result listing comprising the second plurality of result documents.