Populating a structured presentation with new values

• US 8,924,436 B1
• Filed: 04/01/2013
• Issued: 12/30/2014
• Est. Priority Date: 01/16/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Fortuna, Vinicius J., Bihun, Andriy, Laroco, Leonardo A. Jr., Loreto, Daniel, Erbiceanu, Elena, Reynar, Jeffrey C., Hogue, Andrew William, Bhargava, Ankur
• Primary Examiner(s): Spieler, William
• Application Number:
  US13/854,858
• Time in Patent Office: 638 Days
• Field of Search: 707/611
• US Class Current: 707/811
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

Methods, systems, and apparatus, including computer programs stored on computer storage media, for populating a structured presentation with new values. One aspect can be embodied in machine-implemented methods that include the actions of obtaining a plurality of instances and a plurality of attributes; for each instance: identifying one or more documents from an unstructured document collection that are relevant to the instance, where each of the one or more documents include at least a value for an attribute in the plurality of attributes; and establishing a subset of the one or more values as characterizing the instance; and adding each instance, the respective attributes, and the respective subset of values to a structured data collection.

Claims

1. A machine-implemented method comprising:

obtaining a plurality of instances and a plurality of attributes, wherein each instance has one or more attributes of the plurality of attributes as attributes of the instance;

for each attribute of an instance;

identifying a plurality documents from an unstructured document collection that are relevant to the instance, where each of the documents include at least a value for the attribute of the instance;

grouping values of the attribute of the instance into two or more groups; and

establishing a subset of the one or more values of the attribute as characterizing the instance including selecting one group of values from the two or more groups; and

adding each instance, the respective attributes of each instance, and the respective subset of values for the corresponding attributes to a structured data collection.

2. The method of claim 1, where establishing the subset comprises selecting the subset based at least in part on a count of values in each group.

3. The method of claim 1, where establishing the subset comprises selecting the group based at least in part on values in the group meeting a user-specified constraint.

4. The method of claim 1, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a high quality document.

5. The method of claim 1, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a document relevant to another instance in the structured data collection.

6. The method of claim 1, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a document relevant to another attribute in the structured data collection.

7. The method of claim 1, further comprising:

extracting a first candidate value of a first attribute of a first instance from a first electronic document;

extracting a second candidate value of the first attribute of the first instance from a second electronic document;

determining a first likelihood that the first candidate value correctly characterizes the first attribute of the first instance;

determining a second likelihood that the second candidate value correctly characterizes the first attribute of the first instance;

determining that the first likelihood is higher than the second likelihood; and

establishing, in response to determining that the first likelihood is higher than the second likelihood, the first candidate value rather than the second candidate value as characterizing the first instance in the structured data collection.

8. The method of claim 7, where the first likelihood and the second likelihood are determined based on a number of times that the respective candidate value is used to characterize the respective attribute of the respective instance.

9. The method of claim 7, where the first likelihood and the second likelihood are determined based on quality of documents from which the respective candidate value is used to characterize the respective attribute of the respective instance.

10. A system comprising:

a processor; and

computer-readable medium coupled to the processor and having instructions stored thereon, which, when executed by the processor, cause the processor to perform operations comprising;

obtaining a plurality of instances and a plurality of attributes, wherein each instance has one or more attributes of the plurality of attributes as attributes of the instance;

for each attribute of an instance;

identifying a plurality documents from an unstructured document collection that are relevant to the instance, where each of the documents include at least a value for the attribute of the instance;

grouping values of the attribute of the instance into two or more groups; and

establishing a subset of the one or more values of the attribute as characterizing the instance including selecting one group of values from the two or more groups; and

adding each instance, the respective attributes of each instance, and the respective subset of values for the corresponding attributes to a structured data collection.

11. The system of claim 10, where establishing the subset comprises selecting the subset based at least in part on a count of values in each group.

12. The system of claim 10, where establishing the subset comprises selecting the group based at least in part on values in the group meeting a user-specified constraint.

13. The system of claim 10, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a high quality document.

14. The system of claim 10, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a document relevant to another instance in the structured data collection.

15. The system of claim 10, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a document relevant to another attribute in the structured data collection.

16. The system of claim 10, further comprising:

extracting a first candidate value of a first attribute of a first instance from a first electronic document;

extracting a second candidate value of the first attribute of the first instance from a second electronic document;

determining a first likelihood that the first candidate value correctly characterizes the first attribute of the first instance;

determining a second likelihood that the second candidate value correctly characterizes the first attribute of the first instance;

determining that the first likelihood is higher than the second likelihood; and

establishing, in response to determining that the first likelihood is higher than the second likelihood, the first candidate value rather than the second candidate value as characterizing the first instance in the structured data collection.

17. The system of claim 16, where the first likelihood and the second likelihood are determined based on a number of times that the respective candidate value is used to characterize the respective attribute of the respective instance.

18. The system of claim 16, where the first likelihood and the second likelihood are determined based on quality of documents from which the respective candidate value is used to characterize the respective attribute of the respective instance.

19. A computer-readable medium having instructions stored thereon, which, when executed by a processor, cause the professor to perform observations comprising:

obtaining a plurality of instances and a plurality of attributes, wherein each instance has one or more attributes of the plurality of attributes as attributes of the instance;

for each attribute of an instance;

identifying a plurality documents from an unstructured document collection that are relevant to the instance, where each of the documents include at least a value for the attribute of the instance;

grouping values of the attribute of the instance into two or more groups; and

establishing a subset of the one or more values of the attribute as characterizing the instance including selecting one group of values from the two or more groups; and

adding each instance, the respective attributes of each instance, and the respective subset of values for the corresponding attributes to a structured data collection.

20. The computer-readable medium of claim 19, where establishing the subset comprises selecting the subset based at least in part on a count of values in each group.

21. The computer-readable medium of claim 19, where establishing the subset comprises selecting the group based at least in part on values in the group meeting a user-specified constraint.

22. The computer-readable medium of claim 19, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a high quality document.

23. The computer-readable medium of claim 19, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a document relevant to another instance in the structured data collection.

24. The computer-readable medium of claim 19, where establishing the subset comprises selecting the group based at least in part on a value in the group being drawn from a document relevant to another attribute in the structured data collection.

25. The computer-readable medium of claim 19, further comprising:

extracting a first candidate value of a first attribute of a first instance from a first electronic document;

extracting a second candidate value of the first attribute of the first instance from a second electronic document;

determining a first likelihood that the first candidate value correctly characterizes the first attribute of the first instance;

determining a second likelihood that the second candidate value correctly characterizes the first attribute of the first instance;

determining that the first likelihood is higher than the second likelihood; and

establishing, in response to determining that the first likelihood is higher than the second likelihood, the first candidate value rather than the second candidate value as characterizing the first instance in the structured data collection.

26. The computer-readable medium of claim 25, where the first likelihood and the second likelihood are determined based on a number of times that the respective candidate value is used to characterize the respective attribute of the respective instance.

27. The computer-readable medium of claim 25, where the first likelihood and the second likelihood are determined based on quality of documents from which the respective candidate value is used to characterize the respective attribute of the respective instance.