Identifying common co-occurring elements in lists

• US 8,463,782 B1
• Filed: 04/11/2011
• Issued: 06/11/2013
• Est. Priority Date: 07/10/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Upstill, Trystan, Baker, Steven D.
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): BOWEN, RICHARD L
• Application Number:
  US13/084,076
• Time in Patent Office: 792 Days
• Field of Search: None
• US Class Current: 707/736
• 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:

traversing a corpus of documents to identify a plurality of lists within the documents, wherein each list comprises structured data delimited from other data in a document, and wherein each list specifies an enumeration of elements;

selecting a pair of terms based on determining that both terms of the pair are contained in a first quantity of lists that are included in the documents in the corpus, wherein the first quantity is more than a first predetermined quantity, and wherein each list in the first quantity of lists includes more than a second predetermined quantity of terms;

determining a first value that represents a quantity of documents in the corpus that include a list that contains both terms of the pair;

determining a second value that represents a quantity of the documents in the set corpus that include a list that contains at least one of the terms of the pair;

when both terms of the pair are contained in the first quantity of lists that are included in the documents in the corpus, determining a correlation value from the first value and the second value;

determining that the correlation value satisfies a threshold; and

designating, by one or more computers, the pair of terms as potentially non-synonymous terms by adding the pair of terms to a blacklist, based on determining that the correlation value satisfies the threshold, wherein the blacklist is accessed for synonym determination.

2. The method of claim 1, comprising selecting a subset of documents in the corpus,

wherein the first value represents a quantity of documents in the subset that include a list that contains both terms of the pair, and

wherein the second value represents a quantity of the documents in the subset that include a list that contains at least one of the terms of the pair.

3. The method of claim 2, wherein selecting a subset of documents in the corpus comprises:

determining an author for each document in the corpus; and

selecting a subset of documents in the corpus that each have a different author.

4. The method of claim 1, wherein selecting a pair of terms comprises:

selecting a particular list included in a particular document in the corpus, wherein the particular list contains a particular set of terms; and

selecting the pair of terms from the particular set of terms.

5. The method of claim 1, wherein:

one or more lists in the plurality of lists comprises a HyperText Markup Language (HTML) ordered list.

6. The method of claim 1, wherein determining a correlation value from the first value and the second value comprises calculating the correlation value by dividing the first value by the second value.

7. The method of claim 1, wherein selecting a pair of terms comprises:

selecting a particular set of terms that is contained in one or more lists that are included in one or more documents in the corpus;

selecting a particular term, from the particular set of terms, for which a quantity of lists that (i) are included in the documents of the corpus and (ii) contain the particular term exceeds a predetermined value; and

selecting a pair of terms that includes the particular term and another term from the particular set.

8. The method of claim 1, comprising:

determining a third value that represents a total quantity of lists included in the documents in the corpus,

wherein the second value represents a quantity of the documents in the corpus that include an list that, among other terms, includes only one of the terms of the pair, and wherein the correlation value satisfies;

correlation value=(first value)*log [(third value)/(second value)].

9. The method of claim 1, wherein one or more lists in the plurality of lists comprise a HyperText Markup Language (HTML) unordered list.

10. The method of claim 1, wherein one or more lists in the plurality of lists comprise a HyperText Markup Language (HTML) definition list.

11. The method of claim 1, wherein one or more lists in the plurality of lists comprise structured data consisting of enumerated pieces of information within a HyperText Markup Language (HTML) page.

12. The method of claim 1, wherein each list in the plurality of lists is identified by list tags, by items in a table, or by items separated by tabs, commas, or semicolons within an associated document.

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

traversing a corpus of documents to identify a plurality of lists within the documents, wherein each list comprises structured data delimited from other data in a document, and wherein each list specifies an enumeration of elements;

selecting a pair of terms based on determining that both terms of the pair are contained in a first quantity of lists that are included in the documents in the corpus, wherein the first quantity is more than a first predetermined quantity, and wherein each list in the first quantity of lists includes more than a second predetermined quantity of terms;

determining a first value that represents a quantity of documents in the corpus that include a list that contains both terms of the pair;

determining a second value that represents a quantity of the documents in the set corpus that include a list that contains at least one of the terms of the pair;

when both terms of the pair are contained in the first quantity of lists that are included in the documents in the corpus, determining a correlation value from the first value and the second value;

determining that the correlation value satisfies a threshold; and

designating the pair of terms as potentially non-synonymous terms by adding the pair of terms to a blacklist, based on determining that the correlation value satisfies the threshold, wherein the blacklist is accessed for synonym determination.

14. The system of claim 13, wherein the operations comprise selecting a subset of documents in the corpus,

wherein the first value represents a quantity of documents in the subset that include a list that contains both terms of the pair, and

wherein the second value represents a quantity of the documents in the subset that include a list that contains at least one of the terms of the pair.

15. The system of claim 14, wherein selecting a subset of documents in the corpus comprises:

determining an author for each document in the corpus; and

selecting a subset of documents in the corpus that each have a different author.

16. The system of claim 13, wherein selecting a pair of terms comprises:

selecting a particular list included in a particular document in the corpus, wherein the particular list contains a particular set of terms; and

selecting the pair of terms from the particular set of terms.

17. The system of claim 13, wherein:

one or more lists in the plurality of lists comprise a HyperText Markup Language (HTML) ordered list, an HTML unordered list, or an HTML definition list.

18. The system of claim 13, wherein determining a correlation value from the first value and the second value comprises calculating the correlation value by dividing the first value by the second value.

19. The system of claim 13, wherein selecting a pair of terms comprises:

selecting a particular set of terms that is contained in one or more lists that are included in one or more documents in the corpus;

selecting a particular term, from the particular set of terms, for which a quantity of lists that (i) are included in the documents of the corpus and (ii) contain the particular term exceeds a predetermined value; and

selecting a pair of terms that includes the particular term and another term from the particular set.

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

determining a third value that represents a total quantity of lists included in the documents in the corpus,

wherein the second value represents a quantity of the documents in the corpus that include an list that, among other terms, includes only one of the terms of the pair, and wherein the correlation value satisfies;

correlation value=(first value)*log [(third value)/(second value)].

28. The medium of claim 20, wherein the operations comprise:

determining a third value that represents a total quantity of lists included in the documents in the corpus,

wherein the second value represents a quantity of the documents in the corpus that include an list that, among other terms, includes only one of the terms of the pair, and wherein the correlation value satisfies;

correlation value=(first value)*log [(third value)/(second value)].

21. A non-transitory computer-readable medium encoded with a computer program comprising instructions that, when executed, operate to cause a computer to perform operations comprising:

traversing a corpus of documents to identify a plurality of lists within the documents, wherein each list comprises structured data delimited from other data in a document, and wherein each list specifies an enumeration of elements;

selecting a pair of terms based on determining that both terms of the pair are contained in a first quantity of lists that are included in the documents in the corpus, wherein the first quantity is more than a first predetermined quantity, and wherein each list in the first quantity of lists includes more than a second predetermined quantity of terms;

determining a first value that represents a quantity of documents in the corpus that include a list that contains both terms of the pair;

determining a second value that represents a quantity of the documents in the set corpus that include a list that contains at least one of the terms of the pair;

when both terms of the pair are contained in the first quantity of lists that are included in the documents in the corpus, determining a correlation value from the first value and the second value;

determining that the correlation value satisfies a threshold; and

designating the pair of terms as potentially non-synonymous terms by adding the pair of terms to a blacklist, based on determining that the correlation value satisfies the threshold, wherein the blacklist is accessed for synonym determination.

22. The medium of claim 21, wherein the operations comprise selecting a subset of documents in the corpus,

wherein the first value represents a quantity of documents in the subset that include a list that contains both terms of the pair, and

wherein the second value represents a quantity of the documents in the subset that include a list that contains at least one of the terms of the pair.

23. The medium of claim 22, wherein selecting a subset of documents in the corpus comprises:

determining an author for each document in the corpus; and

selecting a subset of documents in the corpus that each have a different author.

24. The medium of claim 21, wherein selecting a pair of terms comprises:

selecting a particular list included in a particular document in the corpus, wherein the particular list contains a particular set of terms; and

selecting the pair of terms from the particular set of terms.

25. The medium of claim 21, wherein:

one or more lists in the plurality of lists comprise a HyperText Markup Language (HTML) ordered list, an HTML unordered list, or an HTML definition list.

26. The medium of claim 21, wherein determining a correlation value from the first value and the second value comprises calculating the correlation value by dividing the first value by the second value.

27. The medium of claim 21, wherein selecting a pair of terms comprises:

selecting a particular set of terms that is contained in one or more lists that are included in one or more documents in the corpus;

selecting a particular term, from the particular set of terms, for which a quantity of lists that (i) are included in the documents of the corpus and (ii) contain the particular term exceeds a predetermined value; and

selecting a pair of terms that includes the particular term and another term from the particular set.