Fuzzy data operations

• US 8,484,215 B2
• Filed: 10/23/2009
• Issued: 07/09/2013
• Est. Priority Date: 10/23/2008
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Anderson, Arlen
• Primary Examiner(s): Nguyen, Cindy
• Application Number:
  US12/605,007
• Publication Number:
  US 20100106724A1
• Time in Patent Office: 1,355 Days
• Field of Search: 707/737, 707/780
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/02 using fuzzy logic computing arrangements based on biological models G06N3/00; computing arrangements using knowledge-based models G06N5/00

Abstract

A method for clustering data elements stored in a data storage system includes reading data elements from the data storage system. Clusters of data elements are formed with each data element being a member of at least one cluster. At least one data element is associated with two or more clusters. Membership of the data element belonging to respective ones of the two or more clusters is represented by a measure of ambiguity. Information is stored in the data storage system to represent the formed clusters.

Claims

1. A method for clustering data elements stored in a data storage system, the method including:

reading data elements from the data storage system;

forming clusters of data elements with each data element being a member of at least one cluster and with assignment of a given data element as a member of a given cluster being based at least in part on contents of one or more objects in the given data element;

associating at least one data element with two or more clusters, with memberships of the data element belonging to respective ones of the two or more clusters being represented by a measure of ambiguity that quantifies partial membership of a given data element in a given cluster based at least in part on a comparison between contents of the given data element and contents of at least one other data element in the given cluster, the contents of the given data element including at least one of;

one or more of words in one or more objects in the given data element, and variants of the one or more words;

storing information in the data storage system to represent the formed clusters; and

performing a data operation that uses values of the measure of ambiguity representing the memberships;

wherein the data operation includes a rollup that calculates a weighted subtotal of a quantity of the one or more clusters, the quantity being associated with the data element, and the subtotal being calculated by summing the products of the value of the quantity associated with each of the data elements in the first cluster and the respective value of the measure of ambiguity representing the membership of the data elements in the first cluster.

2. The method of claim 1, further including preserving accounting integrity using values of the measure of ambiguity.

3. The method of claim 2, wherein the preservation of accounting integrity for a given quantity is achieved by weighting the quantity with values of the measure of ambiguity.

4. The method of claim 1, further including calculating an exclusive subtotal of the quantity and an inclusive subtotal of the quantity, the exclusive subtotal being calculated by excluding the data elements in the first cluster that are associated with two or more clusters and the inclusive subtotal being calculated by including the data elements in the first cluster that are associated with two or more clusters.

5. The method of claim 1, wherein values of the measure of ambiguity representing the memberships are established based on a function, the function representing relationships between the data element and the two or more clusters.

6. The method of claim 5, wherein the relationships represented by the function are based on quantified similarities between the data element and elements representing respective ones of the two or more clusters.

7. The method of claim 6, wherein the elements representing the respective ones of the two or more clusters are keys of the respective clusters.

8. The method of claim 1, wherein values of the measure of ambiguity of the data element belonging to each cluster of the two or more clusters are based on observed frequencies of the data element in a reference set.

9. The method of claim 1, wherein each cluster of the two or more clusters represents a different potential error in the data element, and values of the measured ambiguity of the data element belonging to each cluster of the two or more clusters are based on the likelihood of the potential error in the data element represented by each cluster.

10. The method of claim 1, wherein forming data clusters includes forming a plurality of superclusters of data elements and for each supercluster forming clusters of data elements within the supercluster.

11. The method of claim 10, wherein forming each supercluster includes determining matches between objects in different data elements based on a variant relation between the objects in the different data elements.

12. The method of claim 11, wherein the variant relation between a first object and a second object corresponds to a value of a function representing a distance between the first object and the second object being below a predetermined threshold.

13. The method of claim 12, wherein the variant relation is not an equivalence relation.

14. The method of claim 10, wherein at least one data element is in more than one supercluster.

15. The method of claim 1, wherein the measure of ambiguity is affected by the possible alternative assignment of the data element to other clusters.

17. The system of claim 15, further including means for preserving accounting integrity using values of the measure of ambiguity.

18. The system of claim 17, wherein the preservation of accounting integrity for a given quantity is achieved by weighting the quantity with values of the measure of ambiguity.

19. The system of claim 15, further including means for calculating an exclusive subtotal of the quantity and an inclusive subtotal of the quantity, the exclusive subtotal being calculated by excluding the data elements in the first cluster that are associated with two or more clusters and the inclusive subtotal being calculated by including the data elements in the first cluster that are associated with two or more clusters.

20. The system of claim 15, wherein values of the measure of ambiguity representing the memberships are established based on a function, the function representing relationships between the data element and the two or more clusters.

21. The system of claim 20, wherein the relationships represented by the function are based on quantified similarities between the data element and elements representing respective ones of the two or more clusters.

22. The system of claim 21, wherein the elements representing the respective ones of the two or more clusters are keys of the respective clusters.

23. The system of claim 15, wherein values of the measure of ambiguity of the data element belonging to each cluster of the two or more clusters are based on observed frequencies of the data element in a reference set.

24. The system of claim 15, wherein each cluster of the two or more clusters represents a different potential error in the data element, and values of the measured ambiguity of the data element belonging to each cluster of the two or more clusters are based on the likelihood of the potential error in the data element represented by each cluster.

25. The system of claim 15, wherein forming data clusters includes forming a plurality of superclusters of data elements and for each supercluster forming clusters of data elements within the supercluster.

26. The system of claim 25, wherein forming each supercluster includes determining matches between objects in different data elements based on a variant relation between the objects in the different data elements.

27. The system of claim 26, wherein the variant relation between a first object and a second object corresponds to a value of a function representing a distance between the first object and the second object being below a predetermined threshold.

28. The system of claim 27, wherein the variant relation is not an equivalence relation.

29. The system of claim 15, wherein at least one data element is in more than one supercluster.

30. The system of claim 15, wherein the measure of ambiguity is affected by the possible alternative assignment of the data element to other clusters.

16. A system for clustering data elements stored in a data storage system, the system including:

means for reading data elements from the data storage system;

means for forming clusters of data elements with each data element being a member of at least one cluster;

means for associating at least one data element with two or more clusters, with memberships of the data element belonging to respective ones of the two or more clusters being represented by a measure of ambiguity;

means for storing information in the data storage system to represent the formed clusters; and

means for performing a data operation that uses values of the measure of ambiguity representing the memberships;

wherein the data operation includes a rollup that calculates a weighted subtotal of a quantity of the one or more clusters, the quantity being associated with the data element, and the subtotal being calculated by summing the products of the value of the quantity associated with each of the data elements in the first cluster and the respective value of the measure of ambiguity representing the membership of the data elements in the first cluster.

31. A computer-readable storage device storing a computer program for clustering data elements stored in a data storage system, the computer program including instructions for causing a computer to:

read data elements from the data storage system;

form clusters of data elements with each data element being a member of at least one cluster and with assignment of a given data element as a member of a given cluster being based at least in part on contents of one or more objects in the given data element;

associate at least one data element with two or more clusters, with memberships of the data element belonging to respective ones of the two or more clusters being represented by a measure of ambiguity that quantifies partial membership of a given data element in a given cluster based at least in part on a comparison between contents of the given data element and contents of at least one other data element in the given cluster, the contents of the given data element including at least one of;

one or more of words in one or more objects in the given data element, and variants of the one or more words; and

store information in the data storage system to represent the formed clusters; and

perform a data operation that uses values of the measure of ambiguity representing the memberships

wherein the data operation includes a rollup that calculates a weighted subtotal of a quantity of the one or more clusters, the quantity being associated with the data element, and the subtotal being calculated by summing the products of the value of the quantity associated with each of the data elements in the first cluster and the respective value of the measure of ambiguity representing the membership of the data elements in the first cluster.

32. The computer-readable storage device of claim 31, wherein the computer program further includes instructions for causing a computer to preserve accounting integrity using values of the measure of ambiguity.

33. The computer-readable storage device of claim 32, wherein the preservation of accounting integrity for a given quantity is achieved by weighting the quantity with values of the measure of ambiguity.

34. The computer-readable storage device of claim 31, wherein the computer program further includes instructions for causing a computer to calculate an exclusive subtotal of the quantity and an inclusive subtotal of the quantity, the exclusive subtotal being calculated by excluding the data elements in the first cluster that are associated with two or more clusters and the inclusive subtotal being calculated by including the data elements in the first cluster that are associated with two or more clusters.

35. The computer-readable storage device of claim 31, wherein values of the measure of ambiguity representing the memberships are established based on a function, the function representing relationships between the data element and the two or more clusters.

36. The computer-readable storage device of claim 35, wherein the relationships represented by the function are based on quantified similarities between the data element and elements representing respective ones of the two or more clusters.

37. The computer-readable storage device of claim 36, wherein the elements representing the respective ones of the two or more clusters are keys of the respective clusters.

38. The computer-readable storage device of claim 31, wherein values of the measure of ambiguity of the data element belonging to each cluster of the two or more clusters are based on observed frequencies of the data element in a reference set.

39. The computer-readable storage device of claim 31, wherein each cluster of the two or more clusters represents a different potential error in the data element, and values of the measured ambiguity of the data element belonging to each cluster of the two or more clusters are based on the likelihood of the potential error in the data element represented by each cluster.

40. The computer-readable storage device of claim 31, wherein forming data clusters includes forming a plurality of superclusters of data elements and for each supercluster forming clusters of data elements within the supercluster.

41. The computer-readable storage device of claim 40, wherein forming each supercluster includes determining matches between objects in different data elements based on a variant relation between the objects in the different data elements.

42. The computer-readable storage device of claim 41, wherein the variant relation between a first object and a second object corresponds to a value of a function representing a distance between the first object and the second object being below a predetermined threshold.

43. The computer-readable storage device of claim 42, wherein the variant relation is not an equivalence relation.

44. The computer-readable storage device of claim 40, wherein at least one data element is in more than one supercluster.

45. The computer-readable storage device of claim 31, wherein the measure of ambiguity is affected by the possible alternative assignment of the data element to other clusters.

46. A system for clustering data elements stored in a data storage system, the system including:

an input device configured to read data elements from the data storage system;

at least one process configured to cluster data elements stored in a data storage system,

the processing including

forming clusters of data elements with each data element being a member of at least one cluster and with assignment of a given data element as a member of a given cluster being based at least in part on contents of one or more objects in the given data element;

associating at least one data element with two or more clusters, with memberships of the data element belonging to respective ones of the two or more clusters being represented by a measure of ambiguity that quantifies partial membership of a given data element in a given cluster based at least in part on a comparison between contents of the given data element and contents of at least one other data element in the given cluster, the contents of the given data element including at least one of;

one or more of words in one or more objects in the given data element, and variants of the one or more words; and

storing information in the data storage system to represent the formed clusters; and

performing a data operation that uses values of the measure of ambiguity representing the memberships

wherein the data operation includes a rollup that calculates a weighted subtotal of a quantity of the one or more clusters, the quantity being associated with the data element, and the subtotal being calculated by summing the products of the value of the quantity associated with each of the data elements in the first cluster and the respective value of the measure of ambiguity representing the membership of the data elements in the first cluster.

47. The system of claim 46, wherein the processing further includes preserving accounting integrity using values of the measure of ambiguity.

48. The system of claim 47, wherein the preservation of accounting integrity for a given quantity is achieved by weighting the quantity with values of the measure of ambiguity.

49. The system of claim 46, wherein the processing further includes calculating an exclusive subtotal of the quantity and an inclusive subtotal of the quantity, the exclusive subtotal being calculated by excluding the data elements in the first cluster that are associated with two or more clusters and the inclusive subtotal being calculated by including the data elements in the first cluster that are associated with two or more clusters.

50. The system of claim 46, wherein values of the measure of ambiguity representing the memberships are established based on a function, the function representing relationships between the data element and the two or more clusters.

51. The system of claim 50, wherein the relationships represented by the function are based on quantified similarities between the data element and elements representing respective ones of the two or more clusters.

52. The system of claim 51, wherein the elements representing the respective ones of the two or more clusters are keys of the respective clusters.

53. The system of claim 46, wherein values of the measure of ambiguity of the data element belonging to each cluster of the two or more clusters are based on observed frequencies of the data element in a reference set.

54. The system of claim 46, wherein each cluster of the two or more clusters represents a different potential error in the data element, and values of the measured ambiguity of the data element belonging to each cluster of the two or more clusters are based on the likelihood of the potential error in the data element represented by each cluster.

55. The system of claim 46, wherein forming data clusters includes forming a plurality of superclusters of data elements and for each supercluster forming clusters of data elements within the supercluster.

56. The system of claim 55, wherein forming each supercluster includes determining matches between objects in different data elements based on a variant relation between the objects in the different data elements.

57. The system of claim 56, wherein the variant relation between a first object and a second object corresponds to a value of a function representing a distance between the first object and the second object being below a predetermined threshold.

58. The system of claim 57, wherein the variant relation is not an equivalence relation.

59. The system of claim 55, wherein at least one data element is in more than one supercluster.

60. The system of claim 46, wherein the measure of ambiguity is affected by the possible alternative assignment of the data element to other clusters.

61. The system of claim 46, wherein the given data element is a record, the one or more objects in the given data element are one or more fields of the record, and the contents of one or more objects in the given data element include at least one of:

a value from one field, a value from a part of one field, and a value from a combination of more than one field.