Generalized method and system of merging and pruning of data trees

• US 6,757,678 B2
• Filed: 04/12/2001
• Issued: 06/29/2004
• Est. Priority Date: 04/12/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Myllymaki, Jussi Petri
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): Alaubaidi, Haythim J.
• Application Number:
  US09/834,965
• Publication Number:
  US 20020188598A1
• Time in Patent Office: 1,174 Days
• Field of Search: 707/3, 707/6, 707/104.1, 707/530, 707/531, 707/532
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An automated system and associated method for building a comprehensive database of a configurable entity that is available from one or more Web sites, while removing redundancies. The system merges data tree structures that contain redundant data into more tractable data tree structures where those redundancies have been removed. More specifically, a feature of the present system is to automate the process of collecting information from one or more Web sites and convert the raw data into a logically fashioned, non-redundant tree structure. Advantageously, Web users would be able to retrieve information stored on one or more Web pages and locally merge the data.

Claims

1. A method for merging matching information in related documents in a computer and pruning data trees to remove redundant information, comprising:

identifying two or more source documents that share a similar logical data tree structure;

within the two or more source documents identifying matching documents that relate to the same configuable entity;

applying a merge document to the matching documents to merge the matching documents into a resulting tree merge document, and to prune the logical data tree of the resulting document; and

wherein applying the merge document into a resulting tree merge document further comprises specifying a first instruction to select information at a predetermined level in the tree structure from a first matching document.

2. The method of claim 1, wherein applying the merge document comprises identifying a merge data tree structure of the merge document that is similar to the data tree structure.

3. The method of claim 1, wherein identifying comprises identifying two or more web documents.

4. The method of claim 1, wherein applying the merge document comprises specifying a condition that determines whether two source documents relate to the same configurable entity.

5. The method of claim 1, wherein applying the merge document further comprises specifying a second instruction to output only unique elements of the matching documents at a given level in the tree structure.

6. A software program product for merging matching information in related documents in a computer and pruning data trees to remove redundant information, comprising:

means for identifying two or more source documents that share a similar logical data tree structure;

means for identifying matching documents that relate to the same configurable entity within the two or more source documents;

means for applying a merge document to the matching documents to merge the matching documents into a resulting tree merge document, and to prune the logical data tree of the resulting document; and

wherein applying the merge document into a resulting tree merge document further comprises specifying a first instruction to select information at a predetermined level in the tree structure from a first matching document.

7. The software program product of claim 6, wherein the means for applying the merge document comprises means for identifying a merge data tree structure of the merge document that is similar to the data tree structure.

8. The software program product of claim 6, wherein the means for identifying comprises means for identifying two or more web documents.

9. The software program product of claim 6, wherein the means for applying the merge document comprises specifying a condition that determines whether two source documents relate to the same configurable entity.

10. The software program product of claim 6, wherein the means for applying the merge document further comprises means for specifying a second instruction to output only unique elements of the matching documents at a given level in the tree structure.

11. A service for merging matching information in relate documents and pruning data trees to remove redundant information in a computer, comprising:

identifying two or more source documents that share a similar logical data tree structure,

within the two or more source documents identifying matching documents that relate to the same configurable entity;

applying a merge document to the matching documents to merge the matching documents into a resulting tree merge document, and to prune the logical data tree of the resulting document; and

wherein applying the merge document into a resulting tree merge document further comprises specifying a first instruction to select information at a predetermined level the tree structure from a first matching document.

12. The service of claim 11, wherein applying the merge document comprises identifying a merge data tree structure of the merge document that is similar to the data tree structure.

13. The service of claim 11, wherein identifying comprises identifying two or more web documents.

14. The service of claim 11, wherein applying the merge document comprises specifying a condition that determines whether two source documents relate to the same configurable entity.

15. The service of claim 11, wherein applying the merge document further comprises specifying a second instruction to output only unique elements of the matching documents at a given level in the tree structure.

16. A service model for merging matching information in related documents and pruning data trees to remove redundant information in a computer, comprising:

An identification of two or more source documents that share a similar logical data tree structure;

within the two or more source documents identification of matching documents that relate to the same configurable entity;

an application of a merge document to the matching documents to merge the matching documents into a resulting tree merge document, and to prune the logical data tree of the resulting document; and

wherein the application of the merge document into a resulting tree merge document further comprises specification of a first instruction to select information at a predetermined level in the tree structure from a first matching document.

17. The service model of claim 16, wherein the application of the merge document further comprises a specification of a second instruction to output only unique elements of the matching documents at a predetermined level in the tree structure.

18. The service model of claim 16, wherein the application of the merge document comprises an identification of a merge data tree structure of the merge document that is similar to the data tree structure.