Method and apparatus for automatically identifying compunds

• US 8,086,599 B1
• Filed: 01/09/2007
• Issued: 12/27/2011
• Est. Priority Date: 10/24/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Heymans, Maureen
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Singh, Amresh
• Application Number:
  US11/651,282
• Time in Patent Office: 1,813 Days
• Field of Search: 707/6, 707/5, 707/3, 707/721, 707/722
• US Class Current: 707/721
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

One embodiment of the present invention provides a system that automatically identifies compounds, such as bigrams or n-grams. During operation, the system obtains selections of search results which were selected by one or more users, wherein the search results were previously generated by a search engine in response to queries containing search terms. Next, the system forms a set of candidate compounds from the queries, wherein each candidate compound comprises n consecutive terms from a query. Then, for each candidate compound in the set, the system analyzes the selections of search results to calculate a likelihood that the candidate compound is a compound.

Claims

1. A computer-implemented method comprising:

generating a candidate compound from a search query, the candidate compound comprising two or more consecutive terms in the search query;

determining a number of times search results responsive to the search query were previously selected by a user;

determining a number of times search results responsive to the search query and that contain the candidate compound were previously selected by the user; and

determining a likelihood that the candidate compound is a compound using a value produced by dividing the determined number of times search results responsive to the search query and that contain the candidate compound were previously selected by the user by the determined number of times search results responsive to the search query were previously selected by the user.

2. The method of claim 1, wherein a compound is a combination of two or more terms that have a different meaning in combination than the terms do separately.

3. The method of claim 1, further comprising determining whether the candidate compound is a compound by comparing the produced value to a threshold value.

4. The method of claim 3, further comprising determining whether the candidate compound is a strong compound or a weak compound by comparing the produced value to multiple threshold values.

5. The method of claim 1, further comprising determining a number of times search results that are responsive to the search query and that do not contain the candidate compound were previously selected by the user, and determining a likelihood that the candidate compound is not a compound from the number of times search results that are responsive to the search query and that do not contain the candidate compound were previously selected by the user.

6. The method of claim 5, further comprising determining that the candidate compound is not a candidate compound from the likelihood that the candidate compound is not a compound.

7. The method of claim 1, wherein the number of times search results responsive to the search query and that contain the candidate compound were previously selected by the user is a number of times search results responsive to the search query and that contain the candidate compound in a summary of the search result were selected by the user.

8. The method of claim 7, wherein the summary of a search result comprises a section of the search result containing at least one term from the search query and surrounding text.

9. The method of claim 8, wherein the summary of the search result further comprises a title of the search result.

10. The method of claim 1, where a search result is selected by the user when the user views the search result for more than a threshold period of time.

11. The method of claim 1, wherein the likelihood that the candidate compound is a compound is further determined from a context of the compound.

12. The method of claim 11, wherein the context of the compound is one or more terms adjacent to the candidate compound in the search query.

13. The method of claim 12, wherein determining the likelihood that the candidate compound is a compound from the context of the compound includes determining a conditional probability that the candidate compound is a compound given that the context is adjacent to the candidate compound.

14. The method of claim 1, further comprising:

generating the candidate compound from each of a plurality of search queries;

determining a separate likelihood that the candidate compound is a compound from search results responsive to each of the plurality of search queries;

determining an overall likelihood that the candidate compound is a compound from the separate likelihoods.

15. The method of claim 14, wherein determining the overall likelihood comprises averaging a plurality of weights, each weight corresponding to one of the separate likelihoods.

16. The method of claim 1, further comprising determining a score for each of a plurality of search results responsive to the search query based, at least in part, on whether the search result contains the candidate compound.

17. The method of claim 16, further comprising increasing the score for search results containing the candidate compound when the likelihood that the candidate compound is a compound exceeds a threshold value.

18. A system comprising:

one or more computers operable to perform operations comprising;

generating a candidate compound from a search query, the candidate compound comprising two or more consecutive terms in the search query;

determining a number of times search results responsive to the search query were previously selected by a user;

determining a number of times search results responsive to the search query and that contain the candidate compound were previously selected by the user; and

determining a likelihood that the candidate compound is a compound using a value produced by dividing the determined number of times search results responsive to the search query and that contain the candidate compound were previously selected by the user by the determined number of times search results responsive to the search query were previously selected by the user.

19. A computer-readable storage medium storing instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

generating a candidate compound from a search query, the candidate compound comprising two or more consecutive terms in the search query;

determining a number of times search results responsive to the search query were previously selected by a user;

determining a number of times search results responsive to the search query and that contain the candidate compound were previously selected by the user; and

determining a likelihood that the candidate compound is a compound using a value produced by dividing the determined number of times search results responsive to the search query and that contain the candidate compound were previously selected by the user by the number of times search results responsive to the search query were previously selected by the user.