System and method for tree discovery

• US 8,832,012 B2
• Filed: 10/26/2011
• Issued: 09/09/2014
• Est. Priority Date: 01/14/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Sundaravaradan, Naren, Patnaik, Debprakash, Marwah, Manish, Shah, Amip, Ramakrishnan, Naren
• Primary Examiner(s): Chang, Li-Wu
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US13/282,388
• Publication Number:
  US 20120185421A1
• Time in Patent Office: 1,049 Days
• Field of Search: 706/11, 706/45, 706/52, 706 54- 55, 707/10, 707/709, 707/737, 707/756, 707/758, 707/803, 370/252
• US Class Current: 706/45
• CPC Class Codes: G06Q 10/0875 Itemisation or classification of parts, supplies or services, e.g. bill of materials
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: Y02P 90/84 Greenhouse gas [GHG] management systems

Abstract

Tree discovery systems and methods are disclosed. An example of a method is carried out by program code stored on non-transient computer-readable medium and executed by a processor. The method may include identifying in computer-readable medium a first node for a system under consideration, each node in the computer-readable medium representing a characteristic of a component. The method may include selecting at least a second node from the computer-readable medium for the first node. The method may include discovering in the computer-readable medium at least one system tree for the system under consideration based on the first node and the at least second node.

Claims

1. A tree discovery method, the method carried out by program code stored on non-transient computer-readable medium and executed by a processor, the method comprising:

identifying in computer-readable medium a first node for a system under consideration, each node in the computer-readable medium representing a characteristic of a component;

selecting at least a second node from the computer-readable medium for the first node, the at least second node selected from a non-exhaustive sampling of nodes as a child node of the first node contributing more to an impact on the system under consideration than any other child node of the first node; and

discovering in the computer-readable medium at least one system tree for the system under consideration based on the first node and the at least second node.

2. The method of claim 1, wherein a set of second nodes is selected for the first node.

3. The method of claim 2, wherein the set of second nodes is selected if an impact of the first node substantially matches a sum of impacts of all second nodes in the set.

4. The method of claim 3, wherein substantially matches is within a threshold degree of accuracy.

5. The method of claim 1, further comprising estimating impact contribution of the first node based on contribution of each second node.

6. The method of claim 1, further comprising determining a coefficient for each second node selected.

7. The method of claim 1, further comprising sampling the computer-readable medium to identify the at least second node for selecting.

8. The method of claim 7, wherein sampling comprises at least one of identifying generators, identifying candidate trees, identifying a consensus tree, and identifying multi-level trees.

9. A tree discovery system, comprising:

a non-transitory computer readable storage to store a plurality of nodes, each of the plurality of nodes representing a characteristic of a component; and

an analysis engine stored on a non-transitory computer readable medium and executable by a processor, the analysis engine operatively associated with the computer readable storage to identify a first node for a system under consideration, and select at least a second node for the first node, the at least second node selected from a non-exhaustive sampling of nodes as a child node of the first node contributing more to an impact on the system under consideration than any other child node of the first node, wherein at least one system tree is generated for the system under consideration based on the first and second nodes.

10. The system of claim 9, wherein the analysis engine selects a set of second nodes for the first node, the set of second nodes selected based on impact of the first node substantially matching a sum of impacts of all second nodes in the set.

11. The system of claim 9, wherein the analysis engine estimates impact contribution of the first node based on contribution of each second node.

12. The system of claim 9, wherein the analysis engine determines a coefficient for each second node selected.

13. The system of claim 9, wherein the analysis engine samples the computer-readable medium to identify the second node.

14. The system of claim 13, wherein sampling comprises identifying generators, identifying candidate trees, identifying a consensus tree, and identifying multi-level trees.

15. The system of claim 14, wherein identifying generators comprises computing a distribution of other nodes in the generators.

16. The system of claim 14, wherein identifying candidate trees comprises clustering portions of a matrix and removing nodes from the clustered portions.

17. The system of claim 14, wherein identifying a consensus tree comprises identifying clusters in candidate trees and selecting most frequently appearing nodes in each cluster as a final tree.

18. The system of claim 14, wherein identifying multi-level trees comprises superimposing all found trees and computing a transitive reduction to obtain a single tree.

19. A tree discovery system, comprising:

an analysis engine stored on a non-transitory computer readable storage and executable by a processor to identify a first node for a system under consideration, and select at least one second node for the first node, the at least one second node selected from a non-exhaustive sampling of nodes as a child node of the first node contributing more to an impact on the system under consideration than any other child node of the first node; and

a tree generator to discover a system tree for the system under consideration based on the first node and the at least one second node.

20. The system of claim 19, wherein the analysis engine samples the computer-readable medium to identify the at least one second node by identifying generators, identifying candidate trees, identifying a consensus tree, and identifying multi-level trees.