Sub-tree similarity for component substitution

• US 9,817,918 B2
• Filed: 01/14/2011
• Issued: 11/14/2017
• Est. Priority Date: 01/14/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Shah, Amip J, Marwah, Manish
• Primary Examiner(s): Herndon, Heather
• Assistant Examiner(s): VO, CECILE H
• Application Number:
  US13/007,175
• Publication Number:
  US 20120185489A1
• Time in Patent Office: 2,496 Days
• Field of Search: 707737, 707772, 707784, 707797, 707802, 707803, 707899, 707706-709, 707723, 707778, 707829, 707956, 707999102, 707748, 707E17017, 707711, 707751, 707769, 707915, 707999006, 7079991, 707E17012, 707E17087, 707E17089, 707999107, 707E17091, 707714, 370252, 370335, 370342
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: Y02P 90/84 Greenhouse gas [GHG] management systems

Abstract

Systems and methods of determining sub-tree similarity for component substitution. A method includes assigning a similarity metric to a plurality of trees stored in computer-readable media. The method also includes constructing a distance matrix in computer-readable media, the distance being between sub-trees. The method also includes correlating sub-trees in the computer-readable media based on the distance matrix.

Claims

1. A method comprising:

determining, by a system comprising a processor and a non-transitory computer-readable storage medium, a similarity metric representing similarity between a plurality of trees stored in computer-readable media, wherein the determined similarity metric is based on similarities between all nodes of the plurality of trees and is computed based on combining the similarities of the nodes of the plurality of trees;

constructing, by the system, a distance matrix including a distance between sub-trees of the plurality of trees based on the determined similarity metric;

correlating, by the system, the sub-trees based on the distance matrix;

rating, by the system, the sub-trees for a specified parameter;

modifying, by the system, a first tree of the plurality of trees by substituting a first sub-tree in the first tree with a second sub-tree in a second tree of the plurality of trees, the substituting based on the rating and a similarity score representing a similarity between the first and second sub-trees; and

use the modified first tree to modify a manufacture of a device represented by the first tree, wherein the use of the modified first tree causes use of a component represented by the second sub-tree in the manufacture of the device instead of use of a component represented by the first sub-tree.

2. The method of claim 1, wherein a similarity score of one between the first and second sub-trees indicates interchangeable sub-trees.

3. The method of claim 1, wherein a similarity score of zero between the first and second sub-trees indicates no correlation between the first and second sub-trees.

4. The method of claim 1, further comprising:

using domain-based rules to determine similarity scores representing similarities between the sub-trees of the plurality of trees, wherein the domain-based rules include rules based on root node attributes, child node attributes, and topology of the plurality of trees.

5. The method of claim 1, wherein attribute based similarity is determined based on multivariate attributes of the sub-trees.

6. The method of claim 1, wherein model based similarity is determined based on available sub-tree data of the sub-trees.

7. The method of claim 1, wherein the similarity score is asymmetric.

8. The method of claim 1, wherein rating the sub-trees for the specified parameter comprises rating the sub-trees for an environmental impact parameter representing an environmental impact of a respective component represented by each respective sub-tree.

9. The method of claim 1, wherein rating the sub-trees for the specified parameter comprises rating the sub-trees for a performance parameter representing performance of a respective component represented by each respective sub-tree.

10. A system comprising:

a non-transitory computer readable storage to store instructions and a system tree having a plurality of nodes, each of the plurality of nodes in the system tree representing a characteristic of a respective component; and

a processor,

wherein the instructions are executable on the processor to;

determine a similarity metric representing similarity between a plurality of trees including the system tree, wherein the determined similarity metric is based on similarities between all nodes of the plurality of trees and is computed based on combining the similarities of the nodes of the plurality of trees;

construct a distance matrix including a distance between sub-trees of the plurality of trees based on the determined similarity metric;

correlate the sub-trees based on the distance matrix;

rate the sub-trees for a specified parameter;

modify the system tree of the plurality of trees by substituting a first sub-tree in the system tree with a second sub-tree in a second tree of the plurality of trees, the substituting based on the rating and a similarity score representing a similarity between the first and second sub-trees; and

use the modified system tree to cause modification of a manufacture of a device represented by the system tree, wherein the use of the modified system tree causes use of a component represented by the second sub-tree in the manufacture of the device instead of use of a component represented by the first sub-tree.

11. The system of claim 10, wherein a similarity score of one between the first and second sub-trees indicates interchangeable sub-trees, and a similarity score of zero indicates no correlation between the first and second sub-trees.

12. The system of claim 10, wherein the similarity score is used for cluster analysis.

13. The system of claim 10, wherein the instructions are executable on the processor to:

use domain-based rules to determine similarity scores representing similarities between the sub-trees of the plurality of trees, the domain-based rules including rules based on sub-tree attributes.

14. The system of claim 10, wherein attribute based similarity is determined based on multivariate attributes of the sub-trees.

15. The system of claim 10, wherein model based similarity is determined based on available sub-tree data.

16. A non-transitory storage medium storing instructions that upon execution cause a system to:

determine a similarity metric representing similarity between a plurality of trees, wherein the determined similarity metric is based on similarities between all nodes of the plurality of trees and is computed based on combining the similarities of the nodes of the plurality of trees;

construct a distance matrix including a distance between sub-trees of the plurality of trees based on the determined similarity metric;

correlate the sub-trees based on the distance matrix;

rate the sub-trees for a specified parameter;

modify a first tree of the plurality of trees by substituting a first sub-tree in the first tree with a second sub-tree in a second tree of the plurality of trees, the substituting based on the rating and a similarity score representing a similarity between the first and second sub-trees; and

use the modified first tree to cause modification of a manufacture of a device represented by the first tree, wherein the use of the modified first tree causes use of a component represented by the second sub-tree in the manufacture of the device instead of use of a component represented by the first sub-tree.

17. The system of claim 16, wherein the similarity score is used for cluster analysis.