Tolerant and extensible discovery of relationships in data using structural information and data analysis

• US 9,792,351 B2
• Filed: 06/10/2005
• Issued: 10/17/2017
• Est. Priority Date: 06/10/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hernandez-Sherrington, Mauricio Antonio, Ho, Ching-Tien, Roth, Mary Ann, Yan, Lingling
• Primary Examiner(s): NGUYEN, THU N
• Application Number:
  US11/149,851
• Publication Number:
  US 20060282429A1
• Time in Patent Office: 4,512 Days
• Field of Search: None
• CPC Class Codes: G06F 16/288 Entity relationship models

Abstract

Various embodiments of a method, system and article of manufacture to discover relationships among a first set of elements and a second set of elements are provided. At least one metric algorithm is identified based on a metric selection parameter. A raw result is determined based on the at least one metric algorithm, a first specified structural description of the first set of elements and a second specified structural description of the second set of elements. The raw result comprises a plurality of relationship measurements and the raw result is ordered. In some embodiments, a balanced result is produced based on the raw result and a matching strategy algorithm. In other embodiments, the matching strategy algorithm is identified based on a matching strategy selection parameter.

Claims

1. A computer-implemented method of discovering relationships among a first set of elements with respect to a first data source and a second set of elements with respect to a second data source, comprising:

applying a plurality of metric algorithms to a first structural description of the first set of elements and a second structural description of the second set of elements, wherein the first structural description describes a first structure of data in the first data source and the second structural description describes a second structure of data in the second data source, wherein each of the metric algorithms produces a metric result for each pair of elements in the first and the second sets, wherein each of the metric results for each pair of elements comprises a relationship strength value between the pair of elements in the first and second sets, wherein each of the relationship strength values produced using one of the metric algorithms for each pair of elements indicates a strength of a relationship between the pair of elements in the first and second sets that has a well defined meaning when compared with other relationship strength values;

producing raw results that include for each pair of first elements in the first and second sets the relationship strength values produced using the metric algorithms;

determining, for each element from the first set, a balanced result comprising a selected pair of pairs including the element from the first set and a determined element of the elements from the second set that has highest of the relationship strength values from the metric algorithms of the pairs with the element from the first set to produce a balanced result set that are a subset of the raw results, wherein pairs including each element from the first set with elements in the second set other than the determined element in the second set forming the balanced result set are excluded from the balanced results; and

returning the balanced result set.

2. The method of claim 1, wherein the relationship strength value indicates one of a measurement value comprising distance between the pair of elements of the first and second sets, a similarity between the pair of elements of the first and second sets, and a distance between the pair of elements of the first and second sets determined by a distribution analysis.

3. The method of claim 1, wherein the metric algorithms use sample data from the first and second data sources to determine the relationship strength value between the pairs of elements in the first and second sets.

4. The method of claim 1, wherein the first structural description describes the first structure in a first native format used by the first data source and wherein the second structural description describes the second structure in a second native format used by the second data source, further comprising:

translating the first and second structural descriptions from the first and second native formats, respectively, to common formats comprising a first common format structural description and a second common format structural description, wherein the metric algorithms are applied to the first and second common format structural descriptions to produce the metric result.

5. The method of claim 4, further comprising:

converting the elements of the first and second sets in the balanced result set from the common formats to the first and second native formats, respectively.

6. The method of claim 1, wherein applying the metric algorithms further comprises:

providing a naming custom parameter that provides for each specified named element in the first and second structural descriptions a mapping of the specified named elements in the first and second structural descriptions to mapped name components; and

replacing specified named elements in the first and second structural descriptions with the mapped named components in the naming custom parameter.

7. The method of claim 1, further comprising:

receiving indication of a resource budget representing an amount of time to apply the metric algorithms and a matching strategy algorithm to determine the balanced result set; and

selecting the metric algorithms and the matching strategy algorithm from a plurality of metric algorithms and matching strategy algorithms to use that will determine the relationships of elements that satisfy constraints of the resource budget, wherein the selected metric algorithms and the selected matching strategy algorithm comprise the applied metric algorithms and the applied matching strategy algorithm.

8. The method of claim 7, wherein each of the plurality of metric algorithms and matching strategy algorithms are associated with a resource budget value, and wherein selecting the metric algorithms and the matching strategy algorithm comprises selecting one of the metric algorithms and one of the matching strategy algorithms having resource budget values satisfying a resource budget value of the received resource budget.

9. The method of claim 1, wherein the relationship strength values comprise a first result set of relationship strength values, further comprising:

processing the metric results having relationship strength values from the metric algorithms for the pairs of elements in the first and second sets to produce a composite metric result comprising relationship strength values for the pairs of elements in the first and second sets, wherein a matching strategy algorithm processes the composite metric result of relationship strength values for the pairs of elements in the first and second sets to determine element pairs of the first and second sets that represent optimal matches according to a matching criteria.

10. The method of claim 9, wherein the composite metric result for each element pair comprises one of:

an ordering of the relationship strength values for the element pair and a single measurement resulting from an operation on weighted relationship strength values from the metric algorithms.

11. The method of claim 1, wherein the first and second sets of elements comprise metadata describing the first and second data sources, respectively, and wherein the relationship strength values describe a strength of the relationship between pairs of metadata elements of the first and second data sources.

12. The method of claim 1, wherein applying the metric algorithms comprise applying a plurality of m metric algorithms to produce a metric result comprising multiple tuples {S1_i, S2_i, n_1,i . . . n_m,i}, where S1_i and S2_i represent elements from the first and second sets of elements and n_1,i . . . n_m,i are the relationship measurements of elements S1_i and S2_i determined by the m metric algorithms.

13. An article of manufacture comprising a computer usable storage medium embodying instructions executable by a computer for discovering relationships among a first set of elements with respect to a first data source and a second set of elements with respect to a second data source, wherein the instructions cause operations comprising:

applying a plurality of metric algorithms to a first structural description of the first set of elements and a second structural description of the second set of elements, wherein the first structural description describes a first structure of data in the first data source and the second structural description describes a second structure of data in the second data source, wherein each of the metric algorithms produces a metric result for each pair of elements in the first and the second sets, wherein each of the metric results for each pair of elements comprises a relationship strength value between the pair of elements in the first and second sets, wherein each of the relationship strength values produced using one of the metric algorithms for each pair of elements indicates a strength of a relationship between the pair of elements in the first and second sets that has a well defined meaning when compared with other relationship strength values;

producing raw results that include for each pair of first elements in the first and second sets the relationship strength values produced using the metric algorithms;

determining, for each element from the first set, a balanced result comprising a selected pair of pairs including the element from the first set and a determined element of the elements from the second set that has highest of the relationship strength values from the metric algorithms of the pairs with the element from the first set to produce a balanced result set that are a subset of the raw results, wherein pairs including each element from the first set with elements in the second set other than the determined element in the second set forming the balanced result set are excluded from the balanced results; and

returning the balanced result set.

14. The article of manufacture of claim 13, wherein the relationship strength value indicates one of a measurement value comprising distance between the pair of elements of the first and second sets, a similarity between the pair of elements of the first and second sets, and a distance between the pair of elements of the first and second sets determined by a distribution analysis.

15. The article of manufacture of claim 13, wherein the metric algorithms use sample data from the first and second data sources to determine the relationship strength value between the pairs of elements in the first and second sets.

16. The article of manufacture of claim 13, wherein the first structural description describes the first structure in a first native format used by the first data source and wherein the second structural description describes the second structure in a second native format used by the second data source, further comprising:

translating the first and second structural descriptions from the first and second native formats, respectively, to common formats comprising a first common format structural description and a second common format structural description, wherein the metric algorithms are applied to the first and second common format structural descriptions to produce the metric result.

17. The article of manufacture of claim 16, wherein the operations further comprise:

converting the elements of the first and second sets in the balanced result set from the common formats to the first and second native formats, respectively.

18. The article of manufacture of claim 13, wherein applying the metric algorithms further comprises:

providing a naming custom parameter that provides for each specified named element in the first and second structural descriptions a mapping of the specified named elements in the first and second structural descriptions to mapped name components; and

replacing specified named elements in the first and second structural descriptions with the mapped named components in the naming custom parameter.

19. The article of manufacture of claim 13, wherein the operations further comprise:

receiving indication of a resource budget representing an amount of time to apply the metric algorithms and a matching strategy algorithm to determine the balanced result set; and

selecting the metric algorithms and the matching strategy algorithm from a plurality of metric algorithms and matching strategy algorithms to use that will determine the relationships of elements that satisfy constraints of the resource budget, wherein the selected metric algorithms and the selected matching strategy algorithm comprise the applied metric algorithms and the applied matching strategy algorithm.

20. The article of manufacture of claim 19, wherein each of the plurality of metric algorithms and matching strategy algorithms are associated with a resource budget value, and wherein selecting the metric algorithms and the matching strategy algorithm comprises selecting one of the metric algorithms and one of the matching strategy algorithms having resource budget values satisfying a resource budget value of the received resource budget.

21. The article of manufacture of claim 13, wherein the relationship strength values comprise a first result set of relationship strength values, wherein the operations further comprise:

processing the metric results having relationship strength values from the metric algorithms for the pairs of elements in the first and second sets to produce a composite metric result comprising relationship strength values for the pairs of elements in the first and second sets, wherein a matching strategy algorithm processes the composite metric result relationship strength values for the pairs of elements in the first and second set to determine element pairs of the first and second sets that represent optimal matches according to a matching criteria.

22. The article of manufacture of claim 21, wherein the composite metric result for each element pair comprises one of:

an ordering of the relationship strength values for the element pair and a single measurement resulting from an operation on weighted relationship strength values from the metric algorithms.

23. The article of manufacture of claim 13, wherein the first and second sets of elements comprise metadata describing the first and second data sources, respectively, and wherein the relationship strength values describe a strength of the relationship between pairs of metadata elements of the first and second data sources.

24. A computer system for discovering relationships among a first set of elements with respect to a first data source and a second set of elements with respect to a second data source in at least storage system, comprising:

a processor;

a computer readable storage medium having program components executed to perform operations, the operations comprising;

applying a plurality of metric algorithms to a first structural description of the first set of elements and a second structural description of the second set of elements, wherein the first structural description describes a first structure of data in the first data source and the second structural description describes a second structure of data in the second data source, wherein each of the metric algorithms produces a metric result for each pair of elements in the first and the second sets, wherein each of the metric results for each pair of elements comprises a relationship strength value between the pair of elements in the first and second sets, wherein each of the relationship strength values produced using one of the metric algorithms for each pair of elements indicates a strength of a relationship between the pair of elements in the first and second sets that has a well defined meaning when compared with other relationship strength values;

producing raw results that include for each pair of first elements in the first and second sets the relationship strength values produced using the metric algorithms;

determining, for each element from the first set, a balanced result comprising a selected pair of pairs including the element from the first set and a determined element of the elements from the second set that has a highest of the relationship strength values from the metric algorithms of the pairs with the element from the first set to produce a balanced result set that are a subset of the raw results, wherein pairs including each element from the first set with elements in the second set other than the determined element in the second set forming the balanced result set are excluded from the balanced results; and

returning the balanced result set.

25. The computer system of claim 24, wherein the relationship strength value indicates one of a measurement value comprising distance between the pair of elements of the first and second sets, a similarity between the pair of elements of the first and second sets, and a distance between the pair of elements of the first and second sets determined by a distribution analysis.

26. The computer system of claim 24, wherein the metric algorithms use sample data from the first and second data sources to determine the relationship strength value between the pairs of elements in the first and second sets.

27. The computer system of claim 24, wherein the first structural description describes the first structure in a first native format used by the first data source and wherein the second structural description describes the second structure in a second native format used by the second data source, wherein the operations further comprise:

translating the first and second structural descriptions from the first and second native formats, respectively, to common formats comprising a first common format structural description and a second common format structural description, wherein the metric algorithms are applied to the first and second common format structural descriptions to produce the metric result.

28. The computer system of claim 27, wherein the operations further comprise:

converting the elements of the first and second sets in the balanced result set from the common formats to the first and second native formats, respectively.

29. The computer system of claim 24, wherein applying the metric algorithms further comprises:

providing a naming custom parameter that provides for each specified named element in the first and second structural descriptions a mapping of the specified named elements in the first and second structural descriptions to mapped name components; and

replacing specified named elements in the first and second structural descriptions with the mapped named components in the naming custom parameter.

30. The computer system of claim 24, wherein the operations further comprise:

receiving indication of a resource budget representing an amount of time to apply the metric algorithms and a matching strategy algorithm to determine the balanced result set; and

selecting the metric algorithms and the matching strategy algorithm from a plurality of metric algorithms and matching strategy algorithms to use that will determine the relationships of elements that satisfy constraints of the resource budget, wherein the selected metric algorithm and the selected matching strategy algorithm comprise the applied metric algorithm and the applied matching strategy algorithm.

31. The computer system of claim 30, wherein each of the plurality of metric algorithms and matching strategy algorithms are associated with a resource budget value, and wherein selecting the metric algorithms and the matching strategy algorithm comprises selecting one of the metric algorithms and one of the matching strategy algorithms having resource budget values satisfying a resource budget value of the received resource budget.

32. The computer system of claim 24, wherein the relationship strength values comprise a first result set of relationship strength values, wherein the operations further comprise:

processing the metric results having relationship strength values from the metric algorithms for the pairs of elements in the first and second sets to produce a composite metric result comprising relationship strength values for the pairs of elements in the first and second sets, wherein a matching strategy algorithm processes the composite metric result relationship strength values for the pairs of elements in the first and second set to determine element pairs of the first and second sets that represent optimal matches according to a matching criteria.

33. The computer system of claim 32, wherein the relationship strength value in the composite metric result for each element pair comprises one of:

an ordering of the relationship strength values for the element pair and a single measurement resulting from an operation on weighted relationship strength values from the metric algorithms.

34. The computer system of claim 24, wherein the first and second sets of elements comprise metadata describing the first and second data sources, respectively, and wherein the relationship strength values describe a strength of the relationship between pairs of metadata elements of the first and second data sources.