Node similarity for component substitution

• US 8,626,693 B2
• Filed: 01/14/2011
• Issued: 01/07/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: Marwah, Manish, Shah, Amip J
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US13/007,270
• Publication Number:
  US 20120185422A1
• Time in Patent Office: 1,089 Days
• Field of Search: 706/12, 706 46- 48
• US Class Current: 706/47
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Systems and methods of determining node similarity for component substitution. An example of a method may be carried out by program code stored on non-transient computer-readable medium and executed by a processor. The method includes estimating a normalized similarity metric between the plurality of nodes in the system tree and nodes in other trees. The method also includes assigning a similarity score to each compared node using at least one of: domain based rules, attribute based similarity metrics, and machine learning. The method also includes combining results for cluster analysis.

Claims

1. A method of determining node similarity for component substitution, the method carried out by program code stored on non-transient computer-readable medium and executed by a processor, the method comprising:

determining similarity metric values between nodes of a target system tree associated with a target system and nodes in other system trees respectively associated with other systems, wherein each system comprises components and nodes of each system tree represent respective ones of the components of the associated system, wherein the determining comprises

comparing nodes of the target system tree with respective nodes of the other system trees by applying at least one of domain based rules and attribute based similarity metrics to attributes of the system components represented by the nodes being compared, and

assigning a similarity score to each node of the other system trees compared to a respective one of the nodes of the target system tree based on results of the comparing; and

for at least one of the nodes of the target system, identifying replacement ones of the nodes of the other system trees based on their respective assigned similarity scores.

2. The method of claim 1, further comprising rating the nodes based on respective similarity scores, and replacing the at least one node of the target system tree with a respective one of the identified replacement nodes based on the rating.

3. The method of claim 1, wherein domain-based rules uses domain knowledge to construct a set of rules based on node attributes.

4. The method of claim 1, wherein domain-based rules include heuristics related to at least one of databases, nodes within the databases, and contextual information.

5. The method of claim 1, wherein attribute based similarity metrics are based on multivariate attributes for each node.

6. The method of claim 5, wherein the multivariate attributes include at least one of LCS, LCP, Levenshtein distance, Minkowski distance, weights assigned to each attribute, and dot product between two attribute vectors.

7. The method of claim 1, wherein the assigning comprises using a model based similarity metric that is determined based on available node data in assigning the similarity score to each compared node.

8. The method of claim 7, wherein the model based similarity metric uses at least one of textual descriptions of each node, data where similarity between nodes is known, topic models, and contextual metrics.

9. The method of claim 1, wherein the similarity score is used to compute similarity between any two nodes in a database.

10. A system determining node similarity for component substitution, comprising:

a non-transitory computer readable storage to store system trees comprising sets of nodes, wherein a system tree is associated with a respective system, each system comprises components, and nodes of each system tree represent components of the associated system; and

an analysis engine operatively associated with the computer readable storage to perform operations comprising determining similarity metric values between nodes of a target one of the system trees and nodes in other ones of the system trees, wherein the determining comprises

the analysis engine comparing nodes of the target system tree with nodes of the other system trees by applying at least one of domain based rules and attribute based similarity metrics to attributes of the system components represented by the nodes being compared, and

the analysis engine assigning a similarity score to each node of the other system trees compared to a respective one of the nodes of the target system tree based on results of the comparing.

11. The system of claim 10, wherein the analysis engine rates the nodes based on respective similarity scores, and replacing the at least one of the common nodes in the system tree is based on the rating.

12. The system of claim 10, wherein a similarity score of one indicates interchangeable nodes, and a similarity score of zero indicates no match.

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

14. The system of claim 10, wherein domain-based rules uses domain knowledge to construct a set of rules based on node attributes.

15. The system of claim 10, wherein attribute based similarity metrics are determined based on multivariate attributes for each node.

16. The system of claim 10, wherein the analysis engine uses a model based similarity metric that is determined based on available node data in assigning the similarity score to each compared node.

17. The system of claim 10, wherein the similarity score is used to compute similarity between any two nodes in a database.

18. A system for determining node similarity for component substitution, comprising:

an analysis engine operatively associated with a non-transitory computer readable storage to perform operations comprising determining similarity metric values between nodes of a target system tree associated with a target system and nodes in other system trees respectively associated with other systems, wherein each system comprises components and nodes of each system tree represent respective ones of the components of the associated system, wherein the determining comprises

the analysis engine comparing ones of the nodes of the target system tree with respective ones of the nodes of the other system trees by applying at least one of domain based rules and attribute based similarity metrics to attributes of the system components represented by the nodes being compared, and

the analysis engine assigning a similarity score to each node of the other system trees compared to a respective one of the nodes of target system tree based on results of the comparing.

19. The system of claim 18, wherein the similarity score is used for cluster analysis.

20. The system of claim 18, further comprising the analysis engine rating the nodes of the other system trees based on their similarity scores, and the analysis engine replacing the at least one of the common nodes in the system tree based on the rating.