Identifying common co-occurring elements in lists

• US 8,285,738 B1
• Filed: 10/21/2011
• Issued: 10/09/2012
• Est. Priority Date: 07/10/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baker, Steven D., Upstill, Trystan
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): BOWEN, RICHARD L
• Application Number:
  US13/278,728
• Time in Patent Office: 354 Days
• Field of Search: None
• US Class Current: 707/765
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/374 Thesaurus
• CPC Class Codes: G06F 40/237 Lexical tools
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

One embodiment of the present invention provides a system for detecting correlations between terms. During operation, the system identifies one or more lists contained in one or more documents and identifies two terms co-occurring in the lists. The system further determines a correlation between the co-occurring terms, and places the co-occurring terms in a correlated-pair list based on the correlation.

Claims

1. A computer-implemented method comprising:

receiving a pair of terms that includes a term and a candidate synonym of the term;

determining that the terms of the pair have been identified as being potentially non-synonymous;

responsive to determining that the terms of the pair have been identified as being potentially non-synonymous, applying a penalty to the pair of terms, wherein application of the penalty comprises;

determining a first quantity, corresponding to a number of times that users of a search engine have submitted queries that include the term,

determining a second quantity, corresponding to a number of times that the users have switched from a query that includes the term, to an alternative query that includes the candidate synonym and that does not include the term, and

adjusting, based on a relationship between the first quantity and the second quantity, a value that is used to determine whether the terms of the pair are synonyms; and

determining, by one or more computers, whether the terms of the pair are synonyms using the adjusted value.

2. The method of claim 1, wherein application of the penalty further comprises evaluating the pair of terms using data derived from search queries.

3. The method of claim 1, wherein determining that the terms of the pair have been identified as being potentially non-synonymous comprises determining that the terms occur in a list of terms that are potentially non-synonymous.

4. The method of claim 1, wherein application of the penalty further comprises:

determining that the number of times that the users have switched from a query that includes the term, to an alternative query that includes the candidate synonym and that does not include the term, satisfies a predetermined threshold.

5. The method of claim 1, wherein application of the penalty further comprises:

calculating a quotient by dividing the second quantity by the first quantity.

6. The method of claim 1, wherein determining whether the terms of the pair are synonyms comprises determining whether the adjusted value satisfies a threshold.

7. The method of claim 1, wherein the value indicates a level of confidence that the terms of the pair are synonyms, and wherein the adjusted value indicates a reduced level of confidence that the terms of the pair are synonyms.

8. The method of claim 1, wherein the value is a threshold, and wherein the adjusted value is a stricter threshold for determining whether the terms of the pair are synonyms.

9. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a pair of terms that includes a term and a candidate synonym of the term;

determining that the terms of the pair have been identified as being potentially non-synonymous;

responsive to determining that the terms of the pair have been identified as being potentially non-synonymous, applying a penalty to the pair of terms, wherein application of the penalty comprises;

determining a first quantity, corresponding to a number of times that users of a search engine have submitted queries that include the term,

determining a second quantity, corresponding to a number of times that the users have switched from a query that includes the term, to an alternative query that includes the candidate synonym and that does not include the term, and

adjusting, based on a relationship between the first quantity and the second quantity, a value that is used to determine whether the terms of the pair are synonyms; and

determining, by one or more computers, whether the terms of the pair are synonyms using the adjusted value.

10. The computer storage medium of claim 9, wherein application of the penalty further comprises evaluating the pair of terms using data derived from search queries.

11. The computer storage medium of claim 9, wherein determining that the terms of the pair have been identified as being potentially non-synonymous comprises determining that the terms occur in a list of terms that are potentially non-synonymous.

12. The computer storage medium of claim 9, wherein application of the penalty further comprises:

determining that the number of times that the users have switched from a query that includes the term, to an alternative query that includes the candidate synonym and that does not include the term, satisfies a predetermined threshold.

13. The computer storage medium of claim 9, wherein application of the penalty further comprises:

calculating a quotient by dividing the second quantity by the first quantity.

14. The computer storage medium of claim 9, wherein determining whether the terms of the pair are synonyms comprises determining whether the adjusted value satisfies a threshold.

15. The computer storage medium of claim 9, wherein the value indicates a level of confidence that the terms of the pair are synonyms, and wherein the adjusted value indicates a reduced level of confidence that the terms of the pair are synonyms.

16. The computer storage medium of claim 9, wherein the value is a threshold, and wherein the adjusted value is a stricter threshold for determining whether the terms of the pair are synonyms.

17. A system comprising:

one or more computers; and

a non-transitory computer-readable storage medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving a pair of terms that includes a term and a candidate synonym of the term;

determining that the terms of the pair have been identified as being potentially non-synonymous;

responsive to determining that the terms of the pair have been identified as being potentially non-synonymous, applying a penalty to the pair of terms, wherein application of the penalty comprises;

determining a first quantity, corresponding to a number of times that users of a search engine have submitted queries that include the term,

determining a second quantity, corresponding to a number of times that the users have switched from a query that includes the term, to an alternative query that includes the candidate synonym and that does not include the term, and

adjusting, based on a relationship between the first quantity and the second quantity, a value that is used to determine whether the terms of the pair are synonyms; and

determining, by one or more computers, whether the terms of the pair are synonyms using the adjusted value.

18. The system of claim 17, wherein application of the penalty further comprises evaluating the pair of terms using data derived from search queries.

19. The system of claim 17, wherein determining that the terms of the pair have been identified as being potentially non-synonymous comprises determining that the terms occur in a list of terms that are potentially non-synonymous.

20. The system of claim 17, wherein application of the penalty further comprises:

determining that the number of times that the users have switched from a query that includes the term, to an alternative query that includes the candidate synonym and that does not include the term, satisfies a predetermined threshold.

21. The system of claim 17, wherein application of the penalty further comprises:

calculating a quotient by dividing the second quantity by the first quantity.

22. The system of claim 17, wherein determining whether the terms of the pair are synonyms comprises determining whether the adjusted value satisfies a threshold.

23. The system of claim 17, wherein the value indicates a level of confidence that the terms of the pair are synonyms, and wherein the adjusted value indicates a reduced level of confidence that the terms of the pair are synonyms.

24. The system of claim 17, wherein the value is a threshold, and wherein the adjusted value is a stricter threshold for determining whether the terms of the pair are synonyms.