ROBUST WRAPPERS FOR WEB EXTRACTION

• US 20100162097A1
• Filed: 12/24/2008
• Published: 06/24/2010
• Est. Priority Date: 12/24/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: SHA, Fei, BOHANNON, Philip, DALVI, Nilesh
• Granted Patent: US 8,762,829 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 2221/2101 Auditing as a secondary aspect
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

A computer-implemented method to determine a robust wrapper includes developing a model indicative of the temporal history of a document, such as a web document written in a markup language. Based on the developed model, robustness characteristics are determined for a plurality of different wrappers representing associated paths to the data item in a representation of the document. Based on a result of the determining operation, a result wrapper of the plurality of wrappers is provided. The result wrapper has a desired robustness characteristic.

Claims

1. A computer-implemented method to determine a robust wrapper representing a data item of a plurality of data items in a document represented by a markup language, comprising:

based on archival data representative of a temporal history of the document, developing a model indicative of the temporal history;

based on the developed model, determining robustness characteristics for a plurality of different wrappers representing associated paths to the data item in a representation of the document;

based on a result of the determining operation, providing, as a result wrapper, one of the plurality of wrappers that has a desired robustness characteristic.

2. The method of claim 1, wherein the representation of the document relates to a tree having a plurality of nodes, wherein at least one of the nodes represents a markup language tag.

3. The method of claim 2, wherein the temporal history of the document relates at least to an original tree and a plurality of changed trees indicative of trees that appeared during the temporal history of the document that are different from the original tree.

4. The method of claim 3, wherein the developing operation further comprises:

obtaining a plurality of pairs, each one of the plurality of pairs including a first element (T) and a second element (T′

), wherein T is the original tree and T′

is a different one of the plurality of changed trees;

determining a plurality of different change operations indicative of changes made to change T into T′

for each one of the plurality of pairs; and

associating each one of the plurality of different change operations with a probability value indicative of a probability that the associated change operation is applied to the document.

5. The method of claim 4, wherein the developing operation uses gradient descent.

6. The method of claim 4, wherein the plurality of different change operations includes at least one of a group consisting of:

a) removing a node;

b) changing a node; and

c) inserting a node.

7. The method of claim 4, wherein the determining operation comprises:

evaluating the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the document when the document is changed in accordance with the plurality of different change operations;

based on a result from the evaluating operation and the probability values associated with the plurality of different change operations, determining a success/failure probability for each one of the wrappers.

8. The method of claim 7, wherein the providing operation is based on comparing the success/failure probabilities of the plurality of wrappers.

9. The method of claim 1, wherein the plurality of different wrappers are minimal wrappers.

10. A computing system for determining a robust wrapper representing a data item of a plurality of data items in a document represented by a markup language, wherein the computing system is operable to:

based on archival data representative of a temporal history of the document, develop a model indicative of the temporal history;

based on the developed model, determine robustness characteristics for a plurality of different wrappers representing associated paths to the data item in a representation of the document; and

based on a result from the determination of the robustness characteristics, provide, as a result wrapper, one of the plurality of wrappers that has a desired robustness characteristic.

11. The computing system of claim 10, wherein the representation of the document relates to a tree having a plurality of nodes, wherein at least one of the nodes represents a markup language tag.

12. The computing system of claim 11, wherein the temporal history of the document relates at least to an original tree and a plurality of changed trees indicative of trees that appeared during the temporal history of the document that are different from the original tree.

13. The computing system of claim 12, wherein the computing system is further operable to:

obtain a plurality of pairs, each one of the plurality of pairs including a first element (T) and a second element (T′

), wherein T is the original tree and T′

is a different one of the plurality of changed trees;

determine a plurality of different change operations indicative of changes made to change T into T′

for each one of the plurality of pairs; and

associate each one of the plurality of different change operations with a probability value indicative of a probability that the associated change operation is applied to the document.

14. The computing system of claim 13, wherein the computing system is further operable to:

evaluate the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the document when the document is changed in accordance with the plurality of different change operations; and

based on a result from the evaluation of the plurality of wrappers and the probability values associated with the plurality of different change operations, determine a success/failure probability for each one of the wrappers.

15. A computer readable medium embodied in a tangible form including executable computer program code operable to determine a robust wrapper representing a data item of a plurality of data items in a document represented by a markup language, wherein the computer readable medium includes:

executable computer code operable to develop, based on archival data representative of a temporal history of the document, a model indicative of the temporal history;

executable computer code operable to determine, based on the developed model, robustness characteristics for a plurality of different wrappers representing associated paths to the data item in a representation of the document; and

executable computer code operable to provide, based on a result of the determining operation and as a result wrapper, one of the plurality of wrappers that has a desired robustness characteristic.

16. The computer readable medium of claim 15, wherein the representation of the document relates to a tree having a plurality of nodes, wherein at least one of the nodes represents a markup language tag.

17. The computer readable medium of claim 16, wherein the temporal history of the document relates at least to an original tree and a plurality of changed trees indicative of trees that appeared during the temporal history of the document that are different from the original tree.

18. The computer readable medium of claim 17, wherein the computer readable medium further includes:

executable computer code operable to obtain a plurality of pairs, each one of the plurality of pairs including a first element (T) and a second element (T′

), wherein T is the original tree and T′

is a different one of the plurality of changed trees;

executable computer code operable to determine a plurality of different change operations indicative of changes made to change T into T′

for each one of the plurality of pairs; and

executable computer code operable to associate each one of the plurality of different change operations with a probability value indicative of a probability that the associated change operation is applied to the document.

19. The computer readable medium of claim 18, wherein the computer readable medium further includes:

executable computer code operable to evaluate the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the document when the document is changed in accordance with the plurality of different change operations;

executable computer code operable to determine, based on a result from the evaluation of the plurality of wrappers and the probability values associated with the plurality of different change operations, a success/failure probability for each one of the wrappers.