Method and apparatus for rapid identification of column heterogeneity

• US 8,176,016 B1
• Filed: 11/17/2006
• Issued: 05/08/2012
• Est. Priority Date: 11/17/2006
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Dai, Bing Tian, Koudas, Nikolaos, Ooi, Beng Chin, Srivastava, Divesh, Venkatasubramanian, Suresh
• Primary Examiner(s): Kim, Charles
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US11/601,416
• Time in Patent Office: 1,999 Days
• Field of Search: 707/200, 707202-204, 707/10
• US Class Current: 707/688
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A method and apparatus for rapid identification of column heterogeneity in databases are disclosed. For example, the method receives data associated with a column in a database. The method computes a cluster entropy for the data as a measure of data heterogeneity and then determines whether said data is heterogeneous in accordance with the cluster entropy.

Claims

1. A computer-implemented method for identifying data heterogeneity, the method comprising:

receiving data associated with a column in a database;

computing a cluster entropy solely for the data of the column as a measure of data heterogeneity, wherein the cluster entropy is computed by;

determining a plurality of soft clusters from the data;

assigning a probability to each of the plurality of soft clusters equal to a fraction of data points of the data that each of the plurality of soft clusters contains; and

computing the cluster entropy based on a resulting distribution of the plurality of soft clusters, wherein the entropy of the resulting distribution comprises the cluster entropy;

determining, via a processor, whether the data of the column is heterogeneous in accordance with the cluster entropy; and

providing a determination of whether the data of the column is heterogeneous as an output to a user.

2. The computer-implemented method of claim 1, wherein the data points comprise strings of input data that are converted into a plurality of distributions of q-grams.

3. The computer-implemented method of claim 1, wherein the determining the plurality of soft clusters employs an information bottleneck method.

4. The computer-implemented method of claim 3, wherein the computing the cluster entropy further comprises:

incorporating background context data.

5. The computer-implemented method of claim 4, wherein the computing the cluster entropy further comprises:

computing an optimal tradeoff parameter β

*, for controlling a tradeoff between distortion and compression in clustering the data points of the data into the plurality of clusters.

6. A non-transitory computer-readable storage medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform a method for identifying data heterogeneity, comprising:

receiving data associated with a column in a database;

computing a cluster entropy solely for the data of the column as a measure of data heterogeneity, wherein the cluster entropy is computed by;

determining a plurality of soft clusters from the data;

assigning a probability to each of the plurality of soft clusters equal to a fraction of data points of the data that each of the plurality of soft clusters contains; and

computing an entropy of a resulting distribution of the plurality of soft clusters, wherein the entropy of the resulting distribution comprises the cluster entropy; and

determining whether the data of the column is heterogeneous in accordance with the cluster entropy.

7. The non-transitory computer-readable storage medium of claim 6, wherein the data points comprise strings of input data that are converted into a plurality of distributions of q-grams.

8. The non-transitory computer-readable storage medium of claim 6, wherein the determining the plurality of soft clusters employs an information bottleneck method.

9. The non-transitory computer-readable storage medium of claim 8, wherein the computing the cluster entropy further comprises:

incorporating background context data.

10. The non-transitory computer-readable storage medium of claim 9, wherein the computing the cluster entropy further comprises:

computing an optimal tradeoff parameter β

*, for controlling a tradeoff between distortion and compression in clustering the data points of the data into the plurality of clusters.

11. The non-transitory computer-readable storage medium of claim 6, further comprising:

providing a determination of whether the data is heterogeneous as an output.

12. An apparatus for identifying data heterogeneity, the apparatus comprising:

a processor; and

a non-transitory computer-readable storage medium in communication with the processor, the computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by the processor, cause the processor to perform a method comprising;

receiving data associated with a column in a database;

computing a cluster entropy solely for the data of the column as a measure of data heterogeneity, wherein the cluster entropy is computed by;

determining a plurality of soft clusters from the data;

assigning a probability to each of the plurality of soft clusters equal to a fraction of data points of the data that each of the plurality of soft clusters contains; and

computing an entropy of a resulting distribution of the plurality of soft clusters, wherein the entropy of the resulting distribution comprises the cluster entropy; and

determining whether the data of the column is heterogeneous in accordance with the cluster entropy.

13. The apparatus of claim 12, wherein the data points comprise strings of input data that are converted into a plurality of distributions of q-grams.

14. The apparatus of claim 12, wherein the determining whether the data of the column is heterogeneous by employing an information bottleneck method.

15. The apparatus of claim 14, wherein the cluster entropy is further computed by:

incorporating background context data.

16. The apparatus of claim 15, wherein the cluster entropy is further computed by:

computing an optimal tradeoff parameter β

*, for controlling a tradeoff between distortion and compression in clustering the data points of the data into the plurality of clusters.