Multi-dimensional database record compression utilizing optimized cluster models

• US 6,633,882 B1
• Filed: 06/29/2000
• Issued: 10/14/2003
• Est. Priority Date: 06/29/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shanmugasundaram, Jayavel, Fayyad, Usama
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): FILIPCZYK, MARCIN R
• Application Number:
  US09/606,964
• Time in Patent Office: 1,202 Days
• Field of Search: 707/1-7, 707/102, 707/103.R
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Apparatus and method for use in querying a database containing data records. The database is characterized by a compression scheme to provide data clustering information. In accordance with a exemplary embodiment of the invention a functional representation of data clustering is a Gaussian and the queries are performing by integrating the Gaussian corresponding to each of the data clusters over the ranges to determine the sum or the count of data records from the database that fall within the selected ranges. The process chooses a value for the cluster number K. The cluster model is next broken up into areas (tiles) based on user defined parameters. Data from the database is then classified based on the tiling information. A sorted version of the classified data, ordered by cluster number and then by the tile number within the cluster is generated. This data is then evaluated to test the sufficiency of the model created during the clustering.

Claims

1. A method of querying a database containing data records stored in the database comprising the steps of:

a) clustering data from data records having multiple dimensions that are stored on a database to provide an initial cluster model having an initial probability distribution describing data records in the database;

b) comparing the initial probability distribution with a representative sample of records in the database to determine a sufficiency of said initial probability distribution;

c) modifying the cluster model to provide an adjusted cluster model that characterizes the data in the database, said modifying step performed by finding a region within an attribute space of the data records of high discrepancy between the initial cluster model and a data sample gathered from the database and increasing the cluster number of the cluster model and reclustering at least a portion of the data in the database to produce the adjusted cluster model to reduce discrepancies between the initial probability distribution and data sample from the database; and

d) determining a sum or a count of data records from the database falling within specified ranges of the multiple dimensions by integrating a functional representation based on the probablity distribution of the adjusted cluster model over the ranges.

2. The method of claim 1 wherein the functional representation excludes certain data records by identifying outlying data records as not falling within a data cluster.

3. The method of claim 2 wherein the step of determining a sum or a count total adds contributions from the outlying data records to the results of the integrating step.

4. The method of claim 1 wherein the step of providing the functional representation is performed by a clustering step that results in a cluster model having a cluster number K and wherein said cluster number K is adjusted when modifying the cluster model.

5. The method of claim 1 wherein the cluster model is adjusted by comparing the functional representation of the cluster model with data read from the database and improving the functional representation based on the cluster model by increasing the number of clusters based on said comparison.

6. Apparatus for querying a database containing data records comprising:

a) means for providing a functional representation of data clustering for multiple data records stored on a database;

b) means for adjusting a fit between the functional representation and the data in the database to provide a more accurate functional representation of the data clustering by segmenting clusters into cluster segments and comparing an expected data density in the cluster segments based on the initial cluster model with an observed data density of data gathered from the database;

c) means for selecting ranges over dimensions of the data for determining a sum or a count of data records from the database falling within the ranges; and

d) means for determining the sum or the count of data records from the database that fall within the selected ranges by integrating the functional representation from each cluster of a multiple number of clusters over the ranges.

7. The apparatus of claim 6 wherein the means for determining calculates both the sum and the count and further includes means for determining a ratio to find the average value of data records over the ranges.

8. The apparatus of claim 6 additionally comprising a user input for controlling accuracy parameters for making the comparison between the cluster model and sampled data.

9. Data mining apparatus for querying a database containing data records comprising:

a ) a memory device for storing a database comprising multiple data records organized into data fields having a dimension n for storing data record items;

b) a computer having one or more processing units for executing a stored computer program, said computer including a rapid access memory store; and

c) an interface for coupling the memory device for storing the database to the computer to allow records to be retrieved from the database;

wherein

d) said computer executing a stored program having software components including i) a component for providing a first data clustering model for multiple number of data records stored on a database, sampling data from the database, and producing an updated cluster model based on a comparison between the first data clustering model and the sampled data;

ii) a component for selecting ranges over dimensions of the data for determining a sum or a count of data records from the database falling within the ranges; and

iii) a component for integrating a functional representation based on the updated cluster model from each cluster over the ranges to determine the sum or the count of data records from the database that fall within the selected ranges;

wherein an amount of the computer'"'"'s rapid access memory store is allocated for storing outlying data records determined not to fit within any of the K clusters which are counted separately when determining the sum or the count.

10. The apparatus of claim 9 wherein execution of the stored program provides said functional representation by clustering data into a number of clusters K, and wherein said clustering step is performed by allocating an amount of the computer'"'"'s rapid access memory store for storing a cluster model.

11. A method of querying data records containing continuous attributes that are stored in the database;

said method comprising the steps of;

a) defining a data cube over which to query the database by selecting ranges over one or more of the continuous attributes of the data records in a database;

b) providing a functional representation of data clustering from data records stored in the database;

said functional representation identifying a distribution probability of said data records by the steps of;

i) performing an intial clustering of data to provide an initial cluster model;

ii) determining regions of an attribute data space where the initial cluster model does not accurately characterize data in the database; and

iii) reclustering the data to produce a second cluster model which more accurately characterizes the data of the regions of the attribute data space found to not accurately charactaerize data in the database; and

c) determining a count of data records from the database that fall within the data 16 cube by integrating the functional representation of the second cluster model over the selected rangs.

12. The method of claim 11 additionally comprising the step of summing attribute contributions by integrating the value of the functional representation over the data cube.

13. The method of claim 11 wherein the clustering step produces a cluster model comprising a covariance matrix for each of K clusters within the clustering model.

14. The method of claim 11 wherein the step of reclustering the data increases a cluster number K to provide a better cluster model that more accurately represents the data in the database.

15. The method of claim 14 wherein one or more regions of the attribute data space not accurately characterizing the data are chosen as cluster means in the second cluster model.

16. The method of claim 15 wherein the functional representation comprises a mixture model probability density function of the form:

$\mathrm{Pr}<br><br>\left(x\right)=\underset{\mathrm{\lambda <br><br>}=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>W_{\mathrm{\lambda <br><br>}},\mathrm{Pr}<br><br>\left(x|\mathrm{\lambda <br><br>}\right).$

having mixture weights W₁ which represent a fraction of the database represented by a data cluster and wherein the number k is the number of such database clusters.

17. A computer-readable medium having computer executable instructions for performing steps comprising:

a) clustering data from data records having multiple dimensions that are stored on a database to provide an initial cluster model having an initial probability distribution describing data records in the database;

b) comparing the initial probability distribution with a representative sample of records in the database to determine a sufficiency of said initial probability distribution;

c) modifying the cluster model to provide an adjusted cluster model that better characterizes the data in the database, said modifying step performed by finding a region within an attribute space of the data records of high discrepancy between the initial cluster model and a data sample gathered from the database and increasing the cluster number of the cluster model and reclustering at least a portion of the data in the database to produce the adjusted cluster model to reduce discrepancies between the initial probability distribution and data sample from the database; and

d) determining a sum or a count of data records from the database falling within specified ranges of the multiple dimensions by integrating a functional representation based on the probability distribution of the adjusted cluster model over the ranges.

18. The computer readable medium of claim 17 wherein the determining step limits some but not all of the attributes to specific ranges and wherein the integrating step for continuous attributes not limited to a range is performed over an entire range of said attributes.

19. The computer readable medium of claim 18 wherein an additional cluster is added by finding a region within an-attribute space of the data records of high discrepancy between the initial cluster model and a sample of data gathered from the database.

20. The computer readable medium of claim 17 wherein the determining step limits some but not all of the attributes to specific ranges and wherein the integrating step for continuous attributes not limited to a range is performed over an entire range of said attribute.

21. The computer readable medium of claim 17 wherein the functional representation excludes certain data records by identifying outlying data records as not falling within a data cluster.

22. The computer readable medium of claim 21 wherein the step of determining a sum or a count total adds contributions from the outlying data records to the results of the integrating step.

23. For use with a data mining system for evaluating a database made up of data records having multiple attributes;

a clustering process comprising the steps of;

a) choosing a first cluster number to use in clustering data contained in a database;

b) clustering the data records from the database using the first cluster number to produce a database clustering model;

c) evaluating the database clustering model by identifying regions wherein a density of data records in the database differs from data distributions predicted by the database clustering model by;

i) dividing an attribute space of the database into multiple partitions;

ii) assigning a specified number of partitions to each of the multiple data record attributes based upon the database clustering model; and

iii) determining a density of data records within the multiple partitions to evaluate the sufficiency of the database clustering model; and

d) based on the identification of said regions, adjusting the cluster number and again clustering the data within the database to produce a subsequent database clustering model having a different cluster number.

24. The computer readable medium of claim 23 wherein the cluster model is adjusted by comparing the functional representation of the cluster model with data read from the database and improving the functional representation based on the cluster model by increasing the number of clusters based on said comparison.

25. The method of claim 23 wherein the attribute space of the database is divided into roughly equal segments based on the pre-established database clustering model.

26. The method of claim 23 wherein the total number of partitions into which the database attribute space is divided is determined from a desired number of data points per partition and the number of data records from the database used while clustering the data records to form the database clustering model.

27. The method of claim 23 wherein the step of determining a density of records is performed by scanning the database and assigning data records to different partitions and then comparing a count of data records assigned to a partition with a calculated count based upon the existing database clustering model.

28. The method of claim 26 wherein the total number of partitions into which the database attribute space is divided is determined from a desired number of data points per partition and the number of data records from the database used while clustering the data records to form the database clustering model.

29. The method of claim 23 wherein the database is made up of records having both discrete and continuous data attributes and wherein the partitions are assigned to the attributes based upon an entropy value for the attribute from the existing database clustering model.

30. The method of claim 29 wherein the step of changing the cluster number is performed by ranking differences between the assigned data records and the calculated count for the multiple partitions into which the database attribute space is divided.

31. The method of claim 26 wherein the database is made up of records having both discrete and continuous data attributes and wherein the partitions are assigned to the attributes based upon an entropy value for the attribute from the existing database clustering model.

32. The method of claim 23 wherein the step of adjusting the cluster number increases the clustering number by adding a new cluster having value based upon a ranking of a difference in the record number for a partition predicted from the database clusterin and a number based upon a scanning of the database.

33. The method of claim 32 comprising the step of choosing an emphasis factor which allocates between the continuous and the discrete components in identifying regions of low and high density of data points.

34. Apparatus for use with a data mining system for evaluating a database made up of data records having multiple attributes comprising:

a) means for choosing a first cluster number to use in clustering data contained in a database;

b) means for clustering the data records from the database using the first cluster number to produce a database clustering model;

c) means for evaluating the database clustering model by identifying regions wherein a density of data records in the database differs from data distributions predicted by the database clustering model by;

i) dividing an attribute space of the database into multiple partitions;

ii) assigning a specified number of partitions to each of the multiple data record attributes based upon the database clustering model; and

iii) determining a density of data records within the multiple partitions to evaluate the sufficiency of the database clustering model; and

d) means for adjusting the cluster number based on the identification of said regions and again clustering the data within the database to produce a subsequent database clustering model having a different cluster number.

35. A method of querying a database containing data records stored in the database comprising the steps of:

a) clustering data from data records having multiple attributes including one or more attributes containing continuous, nondiscrete data that are stored on a database to provide an initial cluster model having an initial probability distribution describing data records in the database and wherein each cluster attribute is characterized by a Gaussian functional depiction of the cluster;

b) comparing the initial probability distribution with a representative sample of records in the database to determine a sufficiency of said initial probability distribution;

c) modifying the cluster model to provide an adjusted cluster model that characterizes the data in the database, said modifying step performed by adjusting the cluster model to reduce discrepancies between the initial probability distribution and data sampled from the database; and

d) determining a sum or a count of data records from the database falling within specified ranges of the multiple dimensions by integrating a functional representation based on the probability distribution of the adjusted cluster model over the ranges.

36. The method of claim 35 wherein the determining step limits some but not all of the attributes to specific ranges and wherein the integrating step for continuous attributes not limited to a range is performed over an entire range of said attributes.

37. A method of querying a database containing data records stored in the database comprising the steps of:

a) clustering data from data records having multiple attributes that are stored on a database to provide an initial cluster model having an initial probability distribution describing data records in the database derived from a covariance matrix based on the data in the database;

b) comparing the initial probability distribution with a representative sample of records in the database to determine a sufficiency of said initial probability distribution;

c) modifying the cluster model to provide an adjusted cluster model that characterizes the data in the database, said modifying step performed by adjusting the cluster model to reduce discrepancies between the initial probability distribution and data sampled from the database; and

d) determining a sum or a count of data records from the database falling within specified ranges of the multiple dimensions by integrating a functional representation based on the probability distribution of the adjusted cluster model over the ranges.

38. A computer-readable medium having computer executable instructions for performing steps comprising:

a) clustering data from data records having multiple attributes including one or more attributes containing continuous, nondiscrete data that are stored on a database to provide an initial cluster model having an initial probability distribution describing data records in the database and wherein each cluster attribute is characterized by a Gaussian functional depiction of the cluster;

b) comparing the initial probability distribution with a representative sample of records in the database to determine a sufficiency of said initial probability distribution;

c) modifying the cluster model to provide an adjusted cluster model that characterizes the data in the database, said modifying step performed by adjusting the cluster model to reduce discrepancies between the initial probability distribution and data sampled from the database; and

d) determining a sum or a count of data records from the database falling within specified ranges of the multiple dimensions by integrating a functional representation based on the probability distribution of the adjusted cluster model over the ranges.

39. A computer-readable medium having computer executable instructions for performing steps comprising:

a) clustering data from data records having multiple attributes that are stored on a database to provide an initial cluster model having an initial probability distribution describing data records in the database derived from a covariance matrix based on the data in the database;

b) comparing the initial probability distribution with a representative sample of records in the database to determine a sufficiency of said initial probability distribution;

c) modifying the cluster model to provide an adjusted cluster model that characterizes the data in the database, said modifying step performed by adjusting the cluster model to reduce discrepancies between the initial probability distribution and data sampled from the database; and

d) determining a sum or a count of data records from the database falling within specified ranges of the multiple dimensions by integrating a functional representation based on the probability distribution of the adjusted cluster model over the ranges.