Parallel tree searches for matching multiple, hierarchical data structures

• US 7,058,644 B2
• Filed: 10/07/2002
• Issued: 06/06/2006
• Est. Priority Date: 10/07/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: Click Commerce, Inc. (Huron Consulting Group Incorporated)
• Inventors: Maram, Srinivas, Patchet, Richard, Hooker, David, Narayanan, Ravi
• Primary Examiner(s): Corrielus, Jean
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US10/265,932
• Publication Number:
  US 20040068498A1
• Time in Patent Office: 1,338 Days
• Field of Search: 707/3, 707 6- 7, 707/10, 707100-1041, 715/501.1, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/84 Mapping; Conversion
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods and systems in a data-processing system for matching data contained in a hierarchical data tree structure. One or more sets of data contained within a first data tree structure can be associated with one or more sets of data contained within a second data tree structure, such that the data associated with the first data tree structure is generally utilized to process the data associated with the second data tree structure. The first data tree structure can then be compared in parallel to the second data tree structure beginning with a first root thereof to thereby identify data similarities between the first and second data tree structures based on a predefined search criteria. Finally, one or more matching set of data between the first data tree structure and the second data tree structure can be identified, in response to comparing the first data structure to the second data structure.

Claims

1. A method in a data-processing system for matching data contained in a hierarchical data tree structure, said method comprising the steps of:

associating at least one set of data contained within a first data tree structure to at least one set of data contained within a second data tree structure, wherein said data associated with said first data tree structure is utilized to process data associated with Mid second data tree structure;

comparing said first data tree structure in parallel to said second data tree structure beginning with a first root thereof to thereby identify data similarities between said first and second data tree structures based on a predefined search criteria;

associating at least one conditional expression with at least one tree node of said first data tree structure to further refine said predefined search criteria, wherein said at least one conditional expression is required for a particular operation to occur;

designating at least one tree node of said first data tree structure and at least one tree node of said second data tree structure with a regular expression, wherein said at least one matching set of data comprises at least one of the following;

data matched to software methods;

data matched to stored data for retrieval thereof;

data matched to security attributes associated with a computer network; and

data matched to a location of a physical object referenced by said data; and

identifying at least one matching set of data between said first data tree structure and said second data tree structure, in response to comparing said first data structure in parallel to said second data structure beginning with said first root thereof and based on said predefined search criteria thereby matching multiple and hierarchical data tree structures.

2. The method of claim 1 wherein said first data tree structure comprises an index tree and said second tree comprises an XML document associated with said index tree.

3. The method of claim 1 wherein said at least one matching set of data comprises a plurality of matching sets of data.

4. The method of claim 1 wherein said at least one matching set of data comprises data matched to stored data for retrieval thereof.

5. The method of claim 1 wherein said at least one matching set of data comprises data matched to security attributes associated with a computer network.

6. The method of claim 1 wherein said at least one matching set of data comprises data matched to a location of a physical objected referenced by said data.

7. The method of claim 1 wherein said first data tree structures and said second data tree structure each comprise at least one node containing a wildcard character and wherein said first and second data tree structures further comprise a plurality of rows.

8. A method in a data processing system for matching data contained in a hierarchical data tree structure, said method comprising the steps of:

associating at least one set of data contained within a tree index to at least one set of data contained within an XML document, wherein tree index is utilized to process said XML document;

comparing said tree index in parallel to XML document beginning with a first root thereof to thereby identify data similarities between said tree index and said XML document based on a predefined search criteria;

identifying at least one matching set of data between said tree index and said XML document, in response to comparing said tree index in parallel to said XML document beginning with said first root thereof and based on said predefined search criteria;

associating at least one conditional expression with at least one tree node of said tree index to further refine said predefined search criteria, wherein said at least one conditional expression is required for a particular operation to occur; and

wherein said at least one matching set of data comprises at least one of the following;

data matched to stored data for retrieval thereof;

data matched to software methods;

data matched to security attributes associated with a computer network; and

data matched to a location of a physical object referenced by said data, thereby matching multiple and hierarchical data tree structures.

9. A system for matching data contained in a hierarchical data tree structure, said system comprising:

at least one set of data contained within a first data tree structure associated with at least one set of data contained within a second data tree structure, wherein said data associated with said first data tree structure is utilized to process data associated with said second data tree structure;

comparing module for comparing said first data tree structure in parallel to said second data tree structure beginning with a first root thereof to thereby identify data similarities between said first and second data tree structures based on a predefined search criteria, wherein at least one conditional expression is associated with at least one tree node of said first data tree structure to further refine said predefined search criteria and wherein at least one tree node of said first data tree structure and at least one tree node of said second data tree structure is designated with a regular expression, wherein said at least one conditional expression is required for a particular operation to occurs;

identification module for identifying at least one matching set of data between said first data tree structure and said second data tree structure, in response to comparing said first data structure in parallel to said second data structure beginning with said first root thereof and based on said predefined search criteria, thereby matching multiple and hierarchical data tree structures; and

wherein said at least one matching set of data comprises at least one of the following;

a plurality of matching sets of data;

data matched to stored data for retrieval thereof;

data matched to security attributes associated with a computer network; and

data matched to a location of a physical object referenced by said data.

10. The system of claim 9 wherein said first data tree structure comprises an index tree and said second tree comprises an XML document associated with said index tree.

11. The system of claim 9 wherein said first data tree structure comprises a software method utilized to process said second data tree structure.

12. The system of claim 9 wherein said matching set of data comprises data matched to stored data for retrieval thereof.

13. The system of claim 9 wherein said matching set of data comprises data matched to security attributes associated with a computer network.

14. The system of claim 9 wherein said first data tree structures and said second data tree structure each comprise at least one node containing a wildcard character and wherein said first and second data tree structures further comprise a plurality of rows.