Identifying common co-occurring elements in lists

• US 8,037,086 B1
• Filed: 07/02/2008
• Issued: 10/11/2011
• Est. Priority Date: 07/10/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Upstill, Trystan G., Baker, Steven D.
• Primary Examiner(s): Kim; Charles
• Assistant Examiner(s): BOWEN, RICHARD L
• Application Number:
  US12/166,718
• Time in Patent Office: 1,196 Days
• Field of Search: None
• US Class Current: 707/767
• 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 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;

evaluating the pair of terms using one or more penalty criteria that are only applied to terms that are identified as being potentially non-synonymous, comprising determining a quantity of switches that have occurred between queries that include the term and queries that include the candidate synonym of the term;

selecting, by one or more computers, a first threshold if the pair of terms satisfies the penalty criteria, or a second threshold if the pair of terms does not satisfy the penalty criteria, wherein the first threshold is a same threshold that is applied to pairs of terms that are not identified as being potentially non-synonymous, and wherein the second threshold is higher than the first threshold; and

determining that the terms of the pair are synonyms when the selected threshold is exceeded.

2. The method of claim 1, wherein the 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.

3. The method of claim 1, wherein evaluating the pair of terms using one or more penalty criteria comprises:

determining whether the quantity of switches satisfies a predetermined threshold.

4. The method of claim 1, wherein evaluating the pair of terms using one or more penalty criteria comprises:

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

calculating a ratio by dividing the quantity of switches by the first quantity; and

determining whether the ratio satisfies a predetermined comparison threshold.

5. The method of claim 1, wherein determining that the terms of the pair are synonyms comprises:

determining a confidence value associated with the pair of terms; and

applying the selected threshold to the confidence value.

6. 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;

evaluating the pair of terms using one or more penalty criteria that are only applied to terms that are identified as being potentially non-synonymous, comprising determining a quantity of switches that have occurred between queries that include the term and queries that include the candidate synonym of the term;

selecting a first threshold if the pair of terms satisfies the penalty criteria, or a second threshold if the pair of terms does not satisfy the penalty criteria, wherein the first threshold is a same threshold that is applied to pairs of terms that are not identified as being potentially non-synonymous, and wherein the second threshold is higher than the first threshold; and

determining that the terms of the pair are synonyms when the selected threshold is exceeded.

7. The computer storage medium of claim 6, wherein the 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.

8. The computer storage medium of claim 6, wherein evaluating the pair of terms using one or more penalty criteria comprises:

determining whether the quantity of switches satisfies a predetermined threshold.

9. The computer storage medium of claim 6, wherein evaluating the pair of terms using one or more penalty criteria comprises:

determining a first quantity, representing a number of times that users of a search engine have submitted queries that include the term; and

calculating a ratio by dividing the quantity of switches by the first quantity; and

determining whether the ratio satisfies a predetermined comparison threshold.

10. The computer storage medium of claim 6, wherein determining that the terms of the pair are synonyms comprises:

determining a confidence value associated with the pair of terms; and

applying the selected threshold to the confidence value.

11. A system comprising:

one or more computers; and

a computer-readable 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;

evaluating the pair of terms using one or more penalty criteria that are only applied to terms that are identified as being potentially non-synonymous, comprising determining a quantity of switches that have occurred between queries that include the term and queries that include the candidate synonym of the term;

selecting a first threshold if the pair of terms satisfies the penalty criteria, or a second threshold if the pair of terms does not satisfy the penalty criteria, wherein the first threshold is a same threshold that is applied to pairs of terms that are not identified as being potentially non-synonymous, and wherein the second threshold is higher than the first threshold; and

determining that the terms of the pair are synonyms when the selected threshold is exceeded.

12. The system of claim 11, wherein the 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.

13. The system of claim 11, wherein evaluating the pair of terms using one or more penalty criteria comprises:

determining whether the quantity of switches satisfies a predetermined threshold.

14. The system of claim 11, wherein evaluating the pair of terms using one or more penalty criteria comprises:

determining a first quantity, representing a number of times that users of a search engine have submitted queries that include the term; and

calculating a ratio by dividing the quantity of switches by the first quantity; and

determining whether the ratio satisfies a predetermined comparison threshold.

15. The system of claim 11, wherein determining that the terms of the pair are synonyms comprises:

determining a confidence value associated with the pair of terms; and

applying the selected threshold to the confidence value.