Fuzzy Data Operations

• US 20100106724A1
• Filed: 10/23/2009
• Published: 04/29/2010
• Est. Priority Date: 10/23/2008
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Software Corporation
• Inventors: Anderson, Arlen
• Granted Patent: US 8,484,215 B2
• Time in Patent Office: Days
• 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;

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; and

storing information in the data storage system to represent the formed clusters.

2. The method of claim 1, wherein each value of the measure of ambiguity representing a membership of the data element belonging to a respective one of the two or more clusters is between zero and one.

3. The method of claim 2, wherein values of the measure of ambiguity representing the memberships are related to the likelihood of the data element belonging to the respective ones of the two or more clusters.

4. The method of claim 2, wherein a sum of each value of the measure of ambiguity representing a membership of the data element belonging to a respective one of the two or more clusters is one.

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

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

7. The method of claim 6, further including performing a data operation that uses values of the measure of ambiguity representing the memberships.

8. The method of claim 7, wherein the data operation includes a rollup that calculates a weighted subtotal of a quantity within a first cluster of the one or more clusters, the quantity being associated with the data element, and the subtotal being calculated by summing within the first cluster 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.

9. The method of claim 8, 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.

10. The method of claim 2, 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.

11. The method of claim 10, wherein the relationships represented by the function are related to the likelihood of the data element belonging to respective ones of the two or more clusters.

12. The method of claim 10, 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.

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

14. 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 equal for each cluster.

15. 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.

16. 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.

17. 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.

18. The method of claim 17, 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.

19. The method of claim 18, 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.

20. The method of claim 19, wherein the variant relation is not an equivalence relation.

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

22. 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; and

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

23. A computer-readable medium 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;

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; and

store information in the data storage system to represent the formed clusters.

24. A method for performing a data operation that receives a key and returns one or more data elements from a data storage system, the method including:

determining multiple candidate data elements based on candidate matches between the key and values of one or more search fields of the data elements; and

corroborating the candidate matches based on values of one or more comparison fields of the candidate data elements different from the search fields.

25. The method of claim 24, wherein the data operation includes forming clusters of data elements with each data element being a member of at least one cluster.

26. The method of claim 25, wherein at least one data element is associated 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.

27. The method of claim 26, wherein the data operation includes a rollup that calculates a weighted subtotal of a quantity within a first cluster of the one or more clusters, the quantity being associated with the data element, and the subtotal being calculated by summing within the first cluster 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.

28. The method of claim 27, 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.

29. The method of claim 26, wherein each value of the measure of ambiguity representing a membership of the data element belonging to a respective one of the two or more clusters is between zero and one.

30. The method of claim 29, wherein values of the measure of ambiguity representing the memberships are related to the likelihood of the data element belonging to the respective ones of the two or more clusters.

31. The method of claim 29, 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.

32. The method of claim 31, wherein the relationships represented by the function are related to the likelihood of the data element belonging to respective ones of the two or more clusters.

33. The method of claim 25, further including determining membership of a given data element in a given cluster based on the values of the one or more comparison fields of the given data element.

34. A system for performing a data operation that receives a key and returns one or more data elements from a data storage system, the system including:

means for determining multiple candidate data elements based on candidate matches between the key and values of one or more search fields of the data elements; and

means for corroborating the candidate matches based on values of one or more comparison fields of the candidate data elements different from the search fields.

35. A computer-readable medium storing a computer program for performing a data operation that receives a key and returns one or more data elements from a data storage system, the computer program including instructions for causing a computer to:

determine multiple candidate data elements based on candidate matches between the key and values of one or more search fields of the data elements; and

corroborate the candidate matches based on values of one or more comparison fields of the candidate data elements different from the search fields.

36. A method for measuring data quality of data elements in a data storage system, the method including:

reading data elements from the data storage system;

for each of one or more entries in one or more fields of the data elements, computing a value of a measure of ambiguity for the entry; and

outputting a representation of data quality of the data elements in the data storage system based on the values of the measure of ambiguity.

37. The method of claim 36, wherein computing the value of the measure of ambiguity includes:

comparing the entries in one or more fields of the data elements to reference values;

identifying one or more variants for at least a first entry that is not an exact match to a reference value; and

computing the value of the measure of ambiguity for the first entry based on the variants for the first entry.

38. The method of claim 37, wherein the value of the measure of ambiguity for the first entry is based on the number of variants for the first entry.

39. The method of claim 38, wherein the representation of data quality of the data elements in the data storage system includes a histogram plot of the number of entries having a specified number of variants.

40. The method of claim 39, wherein the specified number of variants is specified as being within a range.

41. The method of claim 38, wherein the representation of data quality of the data elements in the data storage system includes a list of entries having number of variants larger than a predetermined threshold.

42. The method of claim 36, wherein computing the value of the measure of ambiguity includes:

determining respective frequencies of different entries in the one or more fields; and

computing the value of the measure of ambiguity for a first entry based on a relative frequency of the first entry compared to frequencies of other entries.

43. A system for measuring data quality of data elements in a data storage system, the system including:

means for reading data elements from the data storage system;

means for computing, for each of one or more entries in one or more fields of the data elements, a value of a measure of ambiguity for the entry; and

means for outputting a representation of data quality of the data elements in the data storage system based on the values of the measure of ambiguity.

44. A computer-readable medium storing a computer program for measuring data quality of data elements in a data storage system, the computer program including instructions for causing a computer to:

read data elements from the data storage system;

for each of one or more entries in one or more fields of the data elements, compute a value of a measure of ambiguity for the entry; and

output a representation of data quality of the data elements in the data storage system based on the values of the measure of ambiguity.

45. A method for joining data elements from two or more datasets stored in at least one data storage system, the method including:

determining matches between objects in data elements from a first dataset and objects in data elements from a second dataset based on a variant relation between the objects in the data elements from the first dataset and objects in the data elements from the second dataset;

evaluating respective data elements having respective objects determined as matches; and

joining the data elements from the first dataset with the data elements from the second dataset based on the evaluation of data elements.

46. The method of claim 45, 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.

47. The method of claim 46, wherein the variant relation is not an equivalence relation.

48. The method of claim 46, wherein determining a match between an object in a first data element from the first dataset and an object in a second data element in the second dataset includes determining that the variant relation holds between the object in the first data element and the object in the second data element.

49. The method of claim 46, wherein determining a match between an object in a first data element from the first dataset and an object in a second data element in the second dataset includes determining:

that the variant relation holds between the object in the first data element and an object in a third data element in the first dataset, and that the variant relation hold between the object in the third data element and the object in the second data element.

50. The method of claim 45, wherein evaluating respective data elements having respective objects determined as matches includes comparison of objects in the respective data elements other than the respective objects determined as matches.

51. A system for joining data elements from two or more datasets stored in at least one data storage system, the system including:

means for determining matches between objects in data elements from a first dataset and objects in data elements from a second dataset based on a variant relation between the objects in the data elements from the first dataset and objects in the data elements from the second dataset;

means for evaluating respective data elements having respective objects determined as matches; and

means for joining the data elements from the first dataset with the data elements from the second dataset based on the evaluation of data elements.

52. A computer-readable medium storing a computer program for joining data elements from two or more datasets stored in at least one data storage system, the computer program including instructions for causing a computer to:

determine matches between objects in data elements from a first dataset and objects in data elements from a second dataset based on a variant relation between the objects in the data elements from the first dataset and objects in the data elements from the second dataset;

evaluate respective data elements having respective objects determined as matches; and

join the data elements from the first dataset with the data elements from the second dataset based on the evaluation of data elements.