Identifying common co-occurring elements in lists

• US 9,239,823 B1
• Filed: 05/14/2013
• Issued: 01/19/2016
• Est. Priority Date: 07/10/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Upstill, Trystan G., Baker, Steven D.
• Primary Examiner(s): BOWEN, RICHARD L
• Application Number:
  US13/893,462
• Time in Patent Office: 980 Days
• Field of Search: None
• US Class Current: 1/1
• 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:

obtaining, at one or more computers, a pair of terms in a first language, the pair of terms being commonly co-occurring non-synonyms in a corpus of documents, the corpus of documents being in the first language;

determining a set of variations for each term in the pair of terms;

generating a set of known related input pairs based on the sets of variations for each term in the pair of terms;

for each input pair of terms in the set of known related input pairs, translating, by an automatic translation system, each term in the pair of terms into a second language plurality of languages to generate a set of translated terms;

adding, at the one or more computers, the set of translated terms to a blacklist of known non-synonym pairs for at least one of the plurality of languages; and

determining, based on the blacklist of known non-synonym pairs, whether a pair of candidate terms in at least one of the plurality of languages are synonyms.

2. The method of claim 1, wherein determining variations for each term in the pair of terms comprises determining one or more normalized versions of each term in the pair of terms.

3. The method of claim 1, wherein generating a set of known related input pairs based on the sets of variations for each term in the pair comprises calculating a cross-product between the sets of variations for each term in the pair.

4. The method of claim 1, further comprising generating one or more normalized versions of one or more terms in the set of translated terms.

5. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

obtaining, at one or more computers, a pair of terms in a first language, the pair of terms being commonly co-occurring non-synonyms in a corpus of documents, the corpus of documents being in the first language;

determining a set of variations for each term in the pair of terms;

generating a set of known related input pairs based on the sets of variations for each term in the pair of terms;

for each input pair of terms in the set of known related input pairs, translating, by an automatic translation system, each term in the pair of terms into a plurality of languages to generate a set of translated terms;

adding, at the one or more computers, the set of translated terms to a blacklist of known non-synonym pairs for at least one of the plurality of languages; and

determining, based on the blacklist of known non-synonym pairs, whether a pair of candidate terms in at least one of the plurality of languages are synonyms.

6. The system of claim 5, wherein determining variations for each term in the pair of terms comprises determining one or more normalized versions of each term in the pair of terms.

7. The system of claim 5, wherein generating a set of known related input pairs based on the sets of variations for each term in the pair comprises calculating a cross-product between the sets of variations for each term in the pair.

8. The system of claim 5, further comprising generating one or more normalized versions of one or more terms in the set of translated terms.

9. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

obtaining, at one or more computers, a pair of terms in a first language, the pair of terms being commonly co-occurring non-synonyms in a corpus of documents, the corpus of documents being in the first language;

determining a set of variations for each term in the pair of terms;

generating a set of known related input pairs based on the sets of variations for each term in the pair of terms;

for each input pair of terms in the set of known related input pairs, translating, by an automatic translation system, each term in the pair of terms into a plurality of languages to generate a set of translated terms;

adding, at the one or more computers, the set of translated terms to a blacklist of known non-synonym pairs for at least one of the plurality of languages; and

determining, based on the blacklist of known non-synonym pairs, whether a pair of candidate terms in at least one of the plurality of languages are synonyms.

10. The computer-readable medium of claim 9, wherein determining variations for each term in the pair of terms comprises determining one or more normalized versions of each term in the pair of terms.

11. The computer-readable medium of claim 9, wherein generating a set of known related input pairs based on the sets of variations for each term in the pair comprises calculating a cross-product between the sets of variations for each term in the pair.