Multi-dimensional database and data cube compression for aggregate query support on numeric dimensions

• US 6,549,907 B1
• Filed: 04/22/1999
• Issued: 04/15/2003
• Est. Priority Date: 04/22/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shanmugasundaram, Jayavel, Fayyad, Usama
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/296,831
• Time in Patent Office: 1,454 Days
• Field of Search: 707/3-6, 707/205, 707/101, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

An apparatus and method for efficiently compressing contents of a database system to support ad hoc querying and OLAP type aggregation queries. This invention consists of a new compressed representation of the data cube that (a) drastically reduces storage requirements, (b) does not require the discretization hierarchy along each query dimension to be fixed beforehand and (c) treats each dimension as a potential target measure and supports multiple aggregation functions without additional storage costs. The tradeoff is approximate, yet relatively accurate, answers to queries. We outline mechanisms to reduce the error in the approximation. Our performance evaluation indicates that our compression technique effectively addresses the limitation of existing approaches. The basic method relies on representing the contents of the database by a probability distribution consisting of a mixture of Gaussians. Aggregation queries, be they multi-dimensional, conjunctive, or disjunctive, can be answered by performing integration over the probability distribution.

Claims

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

a) providing a functional representation of multiple data clusters from data records stored on a database;

said functional representation identifying a distribution probability of said data records;

b) 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

c) determining a sum or a count of data records from the database that fall within the selected ranges by integrating the functional representation over the ranges for clusters having a functional representation that includes said ranges.

2. The method of claim 1 wherein the records have one or more fields containing continuous or numeric data or fields whose distribution may be modeled with a Gaussian distribution.

3. The method of claim 2 wherein the step of determining ranges limits some but not all of the continuous fields to specific ranges and wherein the integrating step for continuous fields not so limited is over an entire range of said one or more fields.

4. The method of claim 1 additionally comprising the step of counting or summing individual data records from the database not included in the functional representation of data clustering that are treated as outliers.

5. The method of claim 1 wherein the function representation of a data clustering is derived from a covariance matrix based on the data in the database.

6. The method of claim 5 wherein the covariance matrix is an n by n matrix wherein all non-diagonal entries are zero.

7. The method of claim 1 wherein both the sum and the count are determined and their ratio determined to provide an average of the data records within the ranges.

8. The method of claim 1 additionally comprising the step of clustering data in the database to provide a clustering model from which the functional description of multiple data clusters in the database is provided.

9. The method of claim 8 wherein the step of providing the functional representation comprises the steps of computing a mean and a spread for each data dimension of the multiple clusters which form the clustering model and wherein the mean and spread are then used to calculate a functional representation for each dimension.

10. The method of claim 9 wherein the functional representation is a Gaussian based upon the mean and the spread for the dimensions of each of the multiple data clusters.

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

12. The method of claim 11 wherein the step of determining a sum or a count total adds contributions from the outlying data records.

13. The method of claim 12 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 clustering step is performed by allocating an amount of a computer rapid access memory for storing the cluster model that includes the K clusters and an additional step of allocating an additional amount of memory for storing the outlying data records.

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

a) means for providing a functional representation of data clusters representing multiple number of data records stored on a database;

b) 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

c) 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 over the ranges.

15. The apparatus of claim 14 wherein the means for determining determines both the sum and the count and including means for determining a ratio to find the average value of data records over the ranges.

16. 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 functional representation of multiple data clusters for representing multiple number of data records stored on a database;

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 the functional representation 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.

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

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

19. A method of counting 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 count by selecting ranges over one or more of the continuous attributes of the data records in a database;

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

said functional representation identifying a distribution probability of said data records; and

c) determining the count of data records from the database that fall within the data cube by integrating the functional representation of the data clustering over the selected ranges for each of the clusters having a functional representation that includes the selected ranges.

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

21. The method of claim 20 additionally comprising the step of finding an average value of the data records falling within the data cube by taking a ratio of the sum to the count.

22. The method of claim 19 additionally comprising the step of in addition to integrating over the data cube performing a complete scan of the database and counting data records satisfying a search criteria.

23. The method of claim 19 additionally comprising a clustering step that produces a cluster model comprising a covariance matrix for each of K clusters within the clustering model.

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

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

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

25. The method of claim 19 wherein the step of providing the function representation is performed by a server computer and the steps of determining the count and defining the data cube are performed on one or more client computers which may or may not be in communication with the server computer when the determining step is conducted.

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

a) providing a functional representation of data clusters representing data records stored on a database;

said functional representation identifying a distribution probability of said data records;

b) 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

c) determining a sum or a count of data records from the database that fall within the selected ranges by integrating the functional representation of the data clusters over the ranges.

27. The computer readable medium of claim 26 wherein the step of determining ranges limits some but not all of the data fields to specific ranges and wherein the integrating step for fields not so limited is performed over an entire range of said one or more fields.

28. The computer readable medium of claim 26 additionally including computer readable instructions for counting or summing individual data records from the database not included in the functional representation of data clustering.

29. The computer readable medium of claim 26 wherein the computer readable instructions cause the computer to determine both the sum and the count and further comprising computer readable instructions for determining their ratio to provide an average of the data records within the ranges.

30. The computer readable medium of claim 26 further comprising computer executable instructions for clustering data in the database to provide a clustering model from which the functional description of multiple data clusters in the database is provided.

31. The computer readable medium of claim 30 wherein the computer executable instructions provide a functional representation by computing a mean and a spread for each data dimension of the multiple clusters to form the clustering model and wherein the mean and spread are then used to calculate a functional representation for each dimension.

32. The computer readable medium of claim 26 wherein the computer executable instructions that provide a functional representation excludes certain data records by identifying outlying data records as not falling within a data cluster.

33. The computer readable medium of claim 32 wherein the instructions for determining a sum or a count total adds contributions from the outlying data records.

34. The computer readable medium of claim 33 wherein the computer executable instructions provide the functional representation by performing a clustering step that results in a cluster model having a cluster number K and wherein said clustering step is performed by allocating an amount of a computer rapid access memory for storing the cluster model that includes the K clusters and an additional step of allocating an additional amount of memory for storing the outlying data records.

35. A database management system for querying a database containing data records comprising:

a) a memory device for storing a database comprising multiple data records organized into data fields;

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 clustering component for providing a cluster model that includes a functional representation of data clusters representing multiple number of data records stored on a database; and

ii) a query execution component which performs an aggregation query comprising a sum, a count or an average computed from either the actual data stored in the database or from an integration of the available functional representation of the clusters from the clustering model of the data.

36. The database management system of claim 35 wherein the query execution component selects ranges over dimensions of the data for determining a sum or a count of data records from the database falling within the ranges;

and then integrates the functional representation from each cluster of multiple clusters in the clustering model over the ranges to determine the sum or the count of data records from the database that fall within the selected ranges.

37. The database management system of claim 35 wherein the computer is a server computer that exports a compressed form of the database from the cluster model, said database management system comprising multiple client computers including client software components to compute aggregate queries without again accessing data from the server once the compressed form of the database has been communicated to said client.

38. The database management system of claim 35 the query execution component quickly computes approximate answers to the queries and displays results on a user interface of said computer prior to initiating a complete scan of the database to obtain the answer using data in its storage system.