Inverted indices in information extraction to improve records extracted per annotation
A method is provided for information extraction from among a multiplicity of documents each having a corresponding document object model (DOM) comprising: computing signatures associated with nodes of a multiplicity of DOMs corresponding to the multiplicity of documents; producing an index that associates computed signatures to each document that has a DOM that has one or more nodes corresponding to such signature; annotating one or more nodes of a DOM that corresponds to the at least one selected document; wherein the one or more annotated nodes respectively correspond to one or more respective signatures included in the index; and matching the signatures that correspond to the annotated nodes with signatures in the index to determine which documents from the multiplicity of documents have one or more DOM nodes that correspond to one or more of the annotated nodes.
1. a method for information extraction from among a multiplicity of documents each having a corresponding document object model (DOM) comprising:
computing a plurality of signatures for a plurality of nodes of one or more DOMs that are associated with documents of the multiplicity of documents;
wherein each particular signature of the plurality of signatures represents a different path of a node within at least one of the one or more DOMs;
producing an inverted index that associates each particular signature of the plurality of signatures to an identifier of each document that has a DOM that has one or more nodes corresponding to the particular signature;
selecting at least one document from the multiplicity of documents;
annotating a set of one or more nodes of a DOM that is associated with the at least one selected document;
wherein the set of one or more nodes have one or more signatures that match one or more respective signatures of the plurality of signatures included in the inverted index; and
matching the one or more signatures of the set of one or more nodes with the one or more respective signatures of the plurality of signatures in the inverted index to determine a set of documents, from the multiplicity of documents, that have one or more DOM nodes that correspond to the set of one or more nodes;
wherein the set of documents includes at least one document that is different than the selected at least one document;
wherein at least the steps of computing, producing, and matching are performed by one or more computing devices.
2. The method of claim 1 ,
wherein the one or more DOMs correspond to respective HTML documents.
3. The method of claim 1 ,
wherein the one or more DOMs correspond to respective XML documents.
4. The method of claim 1 further including:
computing one or more signatures that respectively correspond to the set of one or more nodes.
5. The method of claim 1 further including:
producing multiple respective clusters of documents from among the multiplicity of documents;
wherein selecting at least one document from the multiplicity of documents includes selecting the at least one document from a cluster of documents.
6. The method of claim 1 further including:
identifying documents from the multiplicity of documents that have DOMs that are structurally similar;
producing multiple respective clusters of documents in which respective clusters contain documents identified as having structurally similar DOMs;
wherein selecting at least one document from the multiplicity of documents includes selecting the at least one document from a cluster of documents.
7. The method of claim 1 further including:
identifying documents from the multiplicity of documents that have DOMs that are structurally similar;
producing multiple respective clusters of documents in which respective clusters contain documents identified as having structurally similar DOMs;
selecting a cluster from which to select the at least one document based at least in part upon a cluster size of the selected cluster.
8. The method of claim 1 ,
wherein matching includes matching to respectively determine which documents from the multiplicity of documents have at least a threshold number of DOM nodes that correspond to the set of one or more nodes.
9. The method of claim 8 further including:
extracting information from documents determined to have at least the threshold number of DOM nodes that correspond to the set of one or more nodes.
10. The method of claim 1 ,
wherein matching includes matching to respectively determine which documents from the multiplicity of documents have at least a threshold number of DOM nodes that correspond to the set of one or more nodes; and further including:
producing a regular expression tree for the at least one annotated document; and
using the regular expression tree to extract information from documents determined to have at least the threshold number of DOM nodes that correspond to the set of one or more nodes.
11. The method of claim 1 ,
wherein computing the plurality of signatures includes computing signatures associated with DOM nodes of every respective document of the multiplicity of documents.
12. The method of claim 1 ,
wherein computing the plurality of signatures includes computing respective hashes of DOM node tree paths that correspond to nodes of the multiplicity of respective DOMs.
13. The method of claim 1 further including:
computing one or more signatures that respectively correspond to the set of one or more nodes;
wherein computing the one or more signatures that respectively correspond to the set of one or more nodes includes computing respective hashes of DOM node tree paths that correspond to the set of one or more nodes.
14. The method of claim 1
wherein computing the plurality of signatures includes computing respective hashes of DOM node tree paths that correspond to nodes of the multiplicity of respective DOMs; further including:
computing one or more signatures that respectively correspond to the set of one or more nodes;
wherein computing the one or more signatures that respectively correspond to the one or more annotated nodes includes computing respective hashes of DOM node tree paths that correspond to the set of one or more nodes.
15. A non-transitory computer readable storage medium encoded with program code to cause a computer system to perform a process for information extraction from among a multiplicity of documents each having a corresponding document object model (DOM) comprising:
computing a plurality of signatures for a plurality of nodes of one or more DOMs that are associated with documents of the multiplicity of documents;
wherein each particular signature of the plurality of signatures represents a different path of a node within at least one of the one or more DOMs;
producing an inverted index that associates each particular signature of the plurality of signatures to an identifier of each document that has a DOM that has one or more nodes corresponding to the particular signature;
selecting at least one document from the multiplicity of documents;
annotating a set of one or more nodes of a DOM that is associated with the at least one selected document;
wherein the set of one or more nodes have one or more signatures that match one or more respective signatures of the plurality of signatures included in the inverted index; and
matching the one or more signatures of the set of one or more nodes with the one or more respective signatures of the plurality of signatures in the inverted index to determine a set of documents, from the multiplicity of documents, that have one or more DOM nodes that correspond to the set of one or more nodes;
wherein the set of documents includes at least one document that is different than the selected at least one document.
16. The non-transitory computer-readable storage medium of claim 15 further including instructions for:
producing multiple respective clusters of documents from among the multiplicity of documents;
wherein selecting at least one document from the multiplicity of documents includes selecting the at least one document from a cluster of documents.
17. The non-transitory computer-readable storage medium of claim 15 further including instructions for:
identifying documents from the multiplicity of documents that have DOMs that are structurally similar;
producing multiple respective clusters of documents in which respective clusters contain documents identified as having structurally similar DOMs;
wherein selecting at least one document from the multiplicity of documents includes selecting the at least one document from a cluster of documents.
18. The non-transitory computer-readable storage medium of claim 15 further including instructions for:
identifying documents from the multiplicity of documents that have DOMs that are structurally similar;
producing multiple respective clusters of documents in which respective clusters contain documents identified as having structurally similar DOMs;
selecting a cluster from which to select the at least one document based at least in part upon a cluster size of the selected cluster.
19. The non-transitory computer-readable storage medium of claim 15 ,
wherein matching includes matching to respectively determine which documents from the multiplicity of documents have at least a threshold number of DOM nodes that correspond to the set of one or more nodes.
20. A method for information extraction from among a multiplicity of documents each having a corresponding document object model (DOM) comprising:
generating a plurality of signatures for a plurality of nodes of one or more DOMs that are associated with documents of the multiplicity of documents;
wherein the plurality of signatures comprises a first signature that represents a first path for a node of at least one of the one or more DOMs;
wherein the plurality of signatures comprises a second signature that represents a second path for a node of at least one of the one or more DOMS;
wherein the first path is different than the second path;
producing an inverted index that associates the first signature to an identifier of each document, of the multiplicity of documents, that has a DOM that has a node with the first path and associates the second signature to an identifier of each document, of the multiplicity of documents, that has a DOM that has a node with the second path;
receiving annotations for a set of one or more nodes of a DOM that is associated with at least one selected document;
wherein each node of the set of one or more nodes has a particular signature that matches a corresponding signature of the plurality of signatures included in the inverted index; and
matching the particular signature of the each node of the set of one or more nodes with the corresponding signatures in the inverted index to determine a set of documents, from the multiplicity of documents, that have one or more DOM nodes that correspond to the set of one or more nodes;
wherein the set of documents includes at least one document that is different than the selected at least one document;
wherein the method is performed by one or more computing devices.