Attribute-value extraction from structured documents

• US 8,645,391 B1
• Filed: 07/02/2009
• Issued: 02/04/2014
• Est. Priority Date: 07/03/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Nigam, Kamal P., Wong, Yuk Wah, Widdows, Dominic, Lokovic, Thomas David
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Tang, Jieying
• Application Number:
  US12/497,176
• Time in Patent Office: 1,678 Days
• Field of Search: 707/999.005, 707/748, 707/749, 707/758, 715/206, 715/234
• US Class Current: 707/748
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for attribute-value extraction from structured documents. In one aspect, a method includes obtaining an initial attribute whitelist, extracting candidate attributes from a first collection of documents, and grouping the candidate attributes. The method further includes calculating a score for each unique attribute in the candidate attributes, generating an expanded attribute whitelist including the initial attributes and each unique attribute having a score that satisfies a threshold, and using the expanded attribute whitelist to identify valid attribute-value pairs. In another aspect, a method includes extracting candidate attribute-value pairs from a collection of documents and identifying one or more features for each candidate attribute-value pair. The method further includes filtering out non valid attribute-value pairs.

Claims

1. A computer-implemented method, comprising:

obtaining an initial attribute whitelist, the initial attribute whitelist including one or more initial attributes;

processing a first collection of documents, wherein each of the documents has content to be displayed and an underlying structure that defines how the content is to be displayed, to identify a plurality of pairings of candidate attributes with candidate values in the documents, wherein each candidate attribute and each candidate value is content found in the content to be displayed;

grouping the candidate attributes into a plurality of groups according to both a particular document in the first collection in which each candidate attribute was identified and the underlying structure in the particular document in the first collection in which each candidate attribute was identified;

calculating a score for each unique attribute in the candidate attributes, where the score reflects a number of groups containing both the unique attribute and an attribute on the initial attribute whitelist;

generating an expanded attribute whitelist, the expanded attribute whitelist including the initial attributes and each unique attribute having a respective score that satisfies a threshold; and

using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values.

2. The method of claim 1, where using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values comprises:

identifying a plurality of pairings of candidate attributes with candidate values from a second collection of structured documents, the pairings of candidate attributes with candidate values identified according to a respective structure of one or more of the documents in the second collection; and

generating a plurality of valid pairings of candidate attributes with candidate values, the generating including, for each pairing of a candidate attribute with a candidate value, determining whether the respective candidate attribute is on the expanded attribute whitelist, and if the candidate attribute is on the expanded attribute whitelist, including the pairing of the candidate attribute with the candidate value in the plurality of valid pairings of candidate attributes with candidate values.

3. The method of claim 1, where using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values comprises:

identifying a plurality of pairings of candidate attributes with candidate values from a second collection of documents, the pairings of candidate attributes with candidate values identified according to a respective structure of one or more of the documents in the second collection;

grouping the pairings of candidate attributes with candidate values according to both a particular document in the second collection in which each pairing of candidate attributes with candidate values was identified and the underlying structure in the particular document in the second collection; and

determining whether a particular pairing of a candidate attribute with a candidate value identified in the documents of the second collection of documents is in a group with a threshold number of pairings of candidate attributes with candidate values that have an attribute on the expanded attribute whitelist, and if so, including the particular pairing of a candidate attribute with a candidate value in the plurality of valid pairings of candidate attributes with candidate values.

4. The method of claim 1, where the score further reflects a number of attributes on the initial attribute whitelist that are in a group with the unique attribute.

5. The method of claim 1, wherein using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values includes comparing a plurality of candidate pairings of candidate attributes with candidate values to attributes on the expanded attribute whitelist.

6. A computer storage device having a computer program stored thereon, the computer program comprising instructions that when executed cause one or more computers to perform actions comprising:

obtaining an initial attribute whitelist, the initial attribute whitelist including one or more initial attributes;

processing a first collection of documents, wherein each of the documents has content to be displayed and an underlying structure that defines how the content is to be displayed, to identify a plurality of pairings of candidate attributes with candidate values in the documents, wherein each candidate attribute and each candidate value is content found in the content to be displayed;

grouping the candidate attributes into a plurality of groups according to both a particular document in the first collection in which each candidate attribute was identified and the underlying structure in the particular document in the first collection in which each candidate attribute was identified;

calculating a score for each unique attribute in the candidate attributes, where the score reflects a number of groups containing both the unique attribute and an attribute on the initial attribute whitelist;

generating an expanded attribute whitelist, the expanded attribute whitelist including the initial attributes and each unique attribute having a respective score that satisfies a threshold; and

using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values.

7. The computer storage device of claim 6, where using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values comprises:

identifying a plurality of pairings of candidate attributes with candidate values from a second collection of documents, the pairings of candidate attributes with candidate values identified according to a respective structure of one or more of the documents in the second collection; and

generating a plurality of valid pairings of candidate attributes with candidate values, the generating including, for each pairing of a candidate attribute with a candidate value, determining whether the respective candidate attribute is on the expanded attribute whitelist, and if the candidate attribute value pair does have an attribute is on the expanded whitelist, including the pairing of the candidate attribute with the candidate value in the plurality of valid pairings of candidate attributes with candidate values.

8. The computer storage device of claim 6, where using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values comprises:

identifying a plurality of pairings of candidate attributes with candidate values from a second collection of documents, the pairings of candidate attributes with candidate values identified according to a respective structure of one or more of the documents in the second collection;

grouping the pairings of candidate attributes with candidate values according to both a particular document in the second collection in which each pairing of candidate attributes with candidate values was identified and the underlying structure in the particular document in the second collection; and

determining whether a particular pairing of a candidate attribute with a candidate value identified in the documents of the second collection of documents is in a group with a threshold number of pairings of candidate attributes with candidate values that have an attribute on the expanded attribute whitelist, and if so, including the particular pairing of a candidate attribute with a candidate value in the plurality of valid pairings of candidate attributes with candidate values.

9. The computer storage device of claim 6, where the score further reflects a number of attributes on the initial attribute whitelist that are in a group with the unique attribute.

10. The computer storage device of claim 6, wherein using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values includes comparing a plurality of candidate pairings of candidate attributes with candidate values to attributes on the expanded attribute whitelist.

11. A system comprising:

one or more computers configured to perform operations comprising;

obtaining an initial attribute whitelist, the initial attribute whitelist including one or more initial attributes;

processing a first collection of documents, wherein each of the documents has content to be displayed and an underlying structure that defines how the content is to be displayed, to identify a plurality of pairings of candidate attributes with candidate values in the documents, wherein each candidate attribute and each candidate value is content found in the content to be displayed;

grouping the candidate attributes into a plurality of groups according to both a particular document in the first collection in which each candidate attribute was extracted identified and the underlying structure in the particular document in the first collection in which each candidate attribute was identified;

calculating a score for each unique attribute in the candidate attributes, where the score reflects a number of groups containing both the unique attribute and an attribute on the initial attribute whitelist;

generating an expanded attribute whitelist, the expanded attribute whitelist including the initial attributes and each unique attribute having a respective score that satisfies a threshold; and

using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values.

12. The system of claim 11, where using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values comprises:

identifying a plurality of pairings of candidate attributes with candidate values from a second collection of documents, the pairings of candidate attributes with candidate values identified according to a respective structure of one or more of the documents in the second collection; and

generating a plurality of valid pairings of candidate attributes with candidate values, the generating including, for each pairing of a candidate attribute with a candidate value, determining whether the respective candidate attribute is on the expanded attribute whitelist, and if the candidate attribute is on the expanded attribute whitelist, including the pairing of the candidate attribute with the candidate value in the plurality of valid pairings of candidate attributes with candidate values.

13. The system of claim 11, where using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values comprises:

processing a second collection of documents, wherein each of the documents has content to be displayed and an underlying structure that defines how the content is to be displayed, to identify a plurality of pairings of candidate attributes with candidate values, wherein each candidate attribute and each candidate value is content found in the content to be displayed;

grouping the candidate attributes identified in the documents of the second collection of documents into a plurality of groups according to both a particular document in the second collection in which each candidate attribute was identified and the underlying structure of the particular document in the second collection; and

determining whether a particular pairing of a candidate attribute with a candidate value identified in the documents of the second collection of documents is in a group with a threshold number of pairings of candidate attributes with candidate values that have an attribute on the expanded attribute whitelist, and if so, including the particular pairing of a candidate attribute with a candidate value in the plurality of valid pairings of candidate attributes with candidate values.

14. The system of claim 11, where the score further reflects a number of attributes on the initial attribute whitelist that are in a group with the unique attribute.

15. The system of claim 11, wherein using the expanded attribute whitelist to identify valid pairings of candidate attributes with candidate values includes comparing a plurality of candidate pairings of candidate attributes with candidate values to attributes on the expanded attribute whitelist.

16. A computer-implemented method, comprising:

obtaining an initial attribute whitelist, the initial attribute whitelist including one or more initial attributes;

processing a first collection of structured documents to identify structures in the structured documents;

identifying a plurality of candidate attributes in the first collection of structured documents based on the identified structures in the structured documents in the first collection;

grouping the candidate attributes into a plurality of groups according to both a particular structured document in the first collection from which each candidate attribute was extracted and a structure in the particular structured document in the first collection;

calculating a score for each unique attribute in the candidate attributes, where the score reflects a number of groups containing the unique attribute and an attribute on the initial attribute whitelist, wherein the score for each unique attribute is calculated according to;

17. The method of claim 16, where using the expanded attribute whitelist to identify valid attribute-value pairs comprises:

extracting a plurality of candidate attribute-value pairs from a second collection of structured documents, the candidate attribute-value pairs identified according to a respective structure of one or more of the structured documents in the second collection; and

generating a plurality of valid attribute-value pairs, the generating including, for each candidate attribute-value pair, determining whether the candidate attribute-value pair has an attribute that is on the expanded attribute whitelist, including the candidate attribute-value pair in the plurality of valid attribute-value pairs.

18. The method of claim 16, wherein using the expanded attribute whitelist to identify valid attribute-value pairs comprises:

extracting a plurality of candidate attribute-value pairs from a second collection of structured documents, the candidate attribute-value pairs identified according to a respective structure of one or more of the structured documents in the second collection;

grouping the candidate attribute-value pairs according to both a particular structured document in the second collection from which each candidate attribute-value pair was extracted and a corresponding structure of that structured document; and

determining whether a candidate attribute-value pair is in a group with a threshold number of attribute-value pairs that have an attribute on the expanded attribute whitelist, and if so, including the candidate attribute-value pair in the plurality of valid attribute-value pairs.

19. The method of claim 16, wherein the score further reflects a number of attributes on the initial attribute whitelist that are in a group with the unique attribute.

20. A computer storage device having a computer program stored thereon, the computer program comprising instructions that when executed cause one or more computers to perform actions comprising:

obtaining an initial attribute whitelist, the initial attribute whitelist including one or more initial attributes;

processing a first collection of structured documents to identify structures in the structured documents;

identifying a plurality of candidate attributes in the first collection of structured documents based on the identified structures in the structured documents in the first collection;

grouping the candidate attributes into a plurality of groups according to both a particular structured document in the first collection from which each candidate attribute was extracted and a structure in the particular structured document;

calculating a score for each unique attribute in the candidate attributes, where the score reflects a number of groups containing the unique attribute and an attribute on the initial attribute whitelist, wherein the score for each unique attribute is calculated according to;

21. The computer storage device of claim 20, where using the expanded attribute whitelist to identify valid attribute-value pairs comprises:

extracting a plurality of candidate attribute-value pairs from a second collection of structured documents, the candidate attribute-value pairs identified according to a respective structure of one or more of the structured documents in the second collection; and

generating a plurality of valid attribute-value pairs, the generating including, for each candidate attribute-value pair, determining whether the candidate attribute-value pair has an attribute that is on the expanded attribute whitelist, and if the candidate attribute-value pair does have an attribute that is on the expanded whitelist, including the candidate attribute-value pair in the plurality of valid attribute-value pairs.

22. The computer storage device of claim 20, where using the expanded attribute whitelist to identify valid attribute-value pairs comprises:

extracting a plurality of candidate attribute-value pairs from a second collection of structured documents, the candidate attribute-value pairs identified according to a respective structure of one or more of the structured documents in the second collection;

grouping the candidate attribute-value pairs according to both a particular structured document in the second collection from which each candidate attribute-value pair was extracted and a corresponding structure of that structured document; and

determining whether a candidate attribute-value pair is in a group with a threshold number of attribute-value pairs that have an attribute on the expanded attribute whitelist, and if so, including the candidate attribute-value pair in the plurality of valid attribute-value pairs.

23. The computer storage device of claim 20, where the score further reflects a number of attributes on the initial attribute whitelist that are in a group with the unique attribute.

24. A system comprising:

one or more computers configured to perform operations comprising;

obtaining an initial attribute whitelist, the initial attribute whitelist including one or more initial attributes;

processing a first collection of structured documents to identify structures in the structured documents;

identifying a plurality of candidate attributes in the first collection of structured documents based on the identified structures in the structured documents in the first collection;

grouping the candidate attributes into a plurality of groups according to both a particular structured document in the first collection from which each candidate attribute was extracted and a structure in that structured document in the first collection;

calculating a score for each unique attribute in the candidate attributes, where the score reflects a number of groups containing the unique attribute and an attribute on the initial attribute whitelist;

wherein the score for each unique attribute is calculated according to;

25. The system of claim 24, where using the expanded attribute whitelist to identify valid attribute-value pairs comprises:

extracting a plurality of candidate attribute-value pairs from a second collection of structured documents, the candidate attribute-value pairs identified according to a respective structure of one or more of the structured documents in the second collection; and

generating a plurality of valid attribute-value pairs, the generating including, for each candidate attribute-value pair, determining whether the candidate attribute-value pair has an attribute that is on the expanded attribute whitelist, and if the candidate attribute-value pair does have an attribute that is on the expanded attribute whitelist, including the candidate attribute-value pair in the plurality of valid attribute-value pairs.

26. The system of claim 24, where using the expanded attribute whitelist to identify valid attribute-value pairs comprises:

extracting a plurality of candidate attribute-value pairs from a second collection of structured documents, the candidate attribute-value pairs identified according to a respective structure of one or more of the structured documents in the second collection;

grouping the candidate attribute-value pairs according to both a particular structured document in the second collection from which each candidate attribute-value pair was extracted and a corresponding structure of that structured document; and

determining whether a candidate attribute-value pair is in a group with a threshold number of attribute-value pairs that have an attribute on the expanded attribute whitelist, and if so, including the candidate attribute-value pair in the plurality of valid attribute-value pairs.

27. The system of claim 24, where the score further reflects a number of attributes on the initial attribute whitelist that are in a group with the unique attribute.