Method and system to identify records that relate to a pre-defined context in a data set

• US 20060161569A1
• Filed: 04/25/2005
• Published: 07/20/2006
• Est. Priority Date: 01/14/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: FatLens, Inc. (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Pardasani, Dhiraj, Khandelwal, Shashikant, Padmanabhan, Ranjit, Meyer, Alex
• Granted Patent: US 7,672,958 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

The present invention provides a method and a system for identifying relevant information in a data set. The method involves the identification of nodes of interest in a tree structure. A node of interest is a node that contains information, which is relevant to a pre-defined context. The method further involves the step of iteratively extracting sub-trees from the tree structure and identifying records in the extracted sub-trees. The sub-tree is a hierarchical structure that shows the relationship of each node of interest with its ancestor nodes in the tree structure. Each record is a group of sub-tree nodes and contains at least one node of interest.

Claims

1. A method for identifying relevant information, which relates to a pre-defined context, from a data set represented in the form of a tree structure, the tree structure being a representation of the data set based on a logical relationship between different data objects in the data set, the method comprising the steps of:

a. identifying nodes of interest in the tree structure, each node of interest being a node that contains information, which is relevant to the pre-defined context;

b. iteratively extracting sub-trees from the tree structure, each sub-tree being a hierarchical structure that shows the relationship of the node of interest with its ancestor nodes in the tree structure; and

c. identifying records in the extracted sub-trees, each record being a group of sub-tree nodes, containing at least one node of interest.

2. The method of claim 1, wherein the step of iteratively extracting sub-trees comprises the steps of:

a. iteratively traversing an upward path from each node of interest to the root of the tree structure; and

b. extracting a sub-tree corresponding to each traversed path.

3. The method of claim 1, wherein the step of identifying the records comprises the steps of:

a. counting the number of times each node appears in the extracted sub-trees;

b. scanning an upward path corresponding to each extracted sub-tree to identify record-parents, the record-parents being the lowest nodes in the sub-trees that have a count greater than one;

c. identifying record-children, the record-children being the nodes in the extracted sub-trees which are the child nodes of the record-parents; and

d. selecting the records, the records comprising the identified record-children and nodes that are descendents of the record-children.

4. The method of claim 3 further comprising the step of iteratively performing the steps of:

a. identifying record-parents that link to more than a pre-defined threshold number of record-children;

b. classifying the identified record-parents as nodes of interest;

c. identifying parent nodes of the record-parents;

d. identifying all child nodes of the identified parents;

e. classifying the identified child nodes as record-parents; and

f. repeating steps c and d of method of claim 3 to select the records.

5. A system for identifying relevant information, which relates to a pre-defined context, from a data set represented in the form of a tree structure, the tree structure being a representation of the data set based on a logical relationship between different data objects in the data set, the system comprising:

a. a node identifier, to identify nodes of interest in the tree structure, each node of interest being a node that contains information, which is relevant to the pre-defined context;

b. a sub-tree extractor, to iteratively extract sub-trees from the tree structure, each sub-tree being a hierarchical structure showing the relationship of the node of interest with its ancestor nodes in the tree structure; and

c. a record recognizer, to identify records, each record being a group of sub-tree nodes, containing at least one node of interest.

6. The system of claim 5, wherein the sub-tree extractor iteratively extracts the sub-trees by iteratively traversing an upward path from each node of interest to the root of the tree structure.

7. The system of claim 5, wherein the record recognizer comprises:

a. a counter, to count the number of times each node appears in the extracted sub-trees;

b. a record-parent identifier, to identify record-parents based on the count, the record-parents being the lowest nodes in the sub-trees that have a count greater than one;

c. a record-children identifier, to identify record-children, the record-children being the nodes in the extracted sub-trees which are the child nodes of the record-parents; and

d. a record selector, to select the records, the records comprising the identified record-children and nodes that are descendents of the record-children.

8. A computer program product for use with a computer, the computer program product comprising a computer usable medium having a computer program code embodied therein to identify relevant information, which relates to a pre-defined context, from a data set represented in the form of a tree structure, the tree structure being a representation of the data set based on a logical relationship between different data objects in the data set, the computer program code performing the steps of:

a. identifying nodes of interest in the tree structure, each node of interest being a node that contains information, which is relevant to the pre-defined context;

b. iteratively extracting sub-trees from the tree structure, each sub-tree being a hierarchical structure that shows the relationship of the node of interest with its ancestor nodes in the tree structure; and

c. identifying records, each record being a group of sub-tree nodes, containing at least one node of interest.

9. The computer program product of claim 8, wherein the computer program code for iteratively extracting sub-trees comprises a computer program code for performing the steps of:

a. iteratively traversing an upward path from each node of interest to the root of the tree structure; and

b. extracting a sub-tree corresponding to each traversed path.

10. The computer program product of claim 8, wherein the computer program code for identifying the records comprises a computer program code for performing the steps of:

a. counting the number of times each node appears in the extracted sub-trees;

b. scanning an upward path corresponding to each extracted sub-tree to identify record-parents, the record-parents being the lowest nodes in the extracted sub-trees that have a count greater than one;

c. identifying record-children, the record-children being the nodes in the extracted sub-trees which are the child nodes of the record-parents; and

d. selecting the records, the records comprising the identified record-children and nodes that are descendents of the record-children.

11. The computer program product of claim 10 further comprising a computer program code for iteratively performing the steps of:

a. identifying record-parents that link to more than a pre-defined threshold number of record-children;

b. classifying the identified record-parents as nodes of interest;

c. identifying parent nodes of the record-parents;

d. identifying all child nodes of the identified parents;

e. classifying the identified child nodes as record-parents; and

f. repeating steps c and d of claim 10 to select the records.