CUBE-BASED PERCENTILE CALCULATION

• US 20080320018A1
• Filed: 06/21/2007
• Published: 12/25/2008
• Est. Priority Date: 06/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Richard J, Chang, Chien-Shen
• Granted Patent: US 7,647,333 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

By dividing data entries among multiple data collections, a data collection comprising a data entry associated with a requested percentile can be determined with reference to the number of data entries within each collection. Initially, the range of values corresponding to the identified data collection can be presented as the value of the requested percentile. Should further detail be required, the value for a requested percentile can be refined by averaging the range, linearly, or otherwise, extrapolating estimated values for the data entries within the identified data collection, or sorting the actual entries according to their values. A relational database can maintain the data entries, each comprising values along one or more dimensions, and an OLAP engine component can maintain a counting of the data entries within the defined data collections.

Claims

1. One or more computer-readable media comprising computer-executable instructions for determining a percentile value of a set of data entries, the computer-executable instructions directed to steps comprising:

dividing the data entries into buckets such that a first data entry, having a first dimension value, is divided into a first bucket, having a first bucket lower bound and a first bucket upper bound, both along a first dimension, if the first dimension value is between the first bucket lower bound and the first bucket upper bound;

defining multiple data collections continuously arranged along the first dimension such that a first data collection has a first data collection lower bound and a first data collection upper bound, both along the first dimension;

associating the first bucket with the first data collection if the first bucket lower bound and the first bucket upper bound are both between the first data collection lower bound and the first data collection upper bound;

counting the data entries divided into the buckets;

aggregating, for the multiple data collections, the counted number of data entries for buckets associated with the multiple data collections such that, if the first bucket is associated with the first data collection, then the counted number of data entries divided into the first bucket is also counted for the first data collection;

identifying, based in part on the aggregated number of data entries for the multiple data collections, a total number of data entries in the set of data entries, and a requested percentile, a relevant data collection comprising a relevant data entry, the relevant data entry associated with the requested percentile; and

determining the percentile value to be one or more values between a relevant data collection lower bound and a relevant data collection upper bound, both along the first dimension.

2. The computer-readable media of claim 1, wherein the determining the percentile value comprises determining the percentile value to be an extrapolated value associated with the relevant data entry, the extrapolated value being based on the relevant data collection lower bound, the relevant data collection upper bound and an aggregated number of data entries within the relevant data collection.

3. The computer-readable media of claim 1, wherein the determining the percentile value comprises determining the percentile value to be a relevant data entry value associated with the relevant data entry, the relevant data entry being determined after sorting data entries within the relevant data collection according to their associated first dimension values.

4. The computer-readable medium of claim 1, wherein the first data entry comprises additional dimension values;

the first bucket has a first bucket lower bound along each of the additional dimensions and a first bucket upper bound along each of the additional dimensions; and

the dividing the data entries into buckets further requires dividing the first data entry into the first bucket if the additional dimensional values are each between the first bucket lower bound along each respective additional dimension and the first bucket upper bound along each respective additional dimension.

5. The computer-readable media of claim 1, wherein the defining the multiple data collections comprises selecting the first data collection lower bound along the first dimension and the first data collection upper bound along the first dimension such that values between the first data collection lower bound along the first dimension and the first data collection upper bound along the first dimension are comparable with respect to an analysis for which the percentile value is being determined.

6. The computer-readable media of claim 1, wherein the set of data entries is maintained in a relational database, and wherein further the counting and the aggregating are performed by an OLAP engine provided with a relational database application that manages the relational database.

7. The computer-readable media of claim 1 further comprising computer-executable instructions directed to enabling selection of the requested percentile and enabling selection of one or more bounds along dimensions other than the first dimension, wherein the requested percentile is directed to values along the first dimension.

8. The computer-readable media of claim 1, wherein the associating, counting, and aggregating are performed for each addition of one or more new data entries to the set of data entries.

9. One or more computer-readable media comprising computer-executable instructions providing for the determination of a percentile value of a set of data entries comprising values along multiple dimensions, the computer-executable instructions directed to steps comprising:

providing an interface for requesting a percentile directed to values along a first dimension, the interface enabling selection of one or more bounds along dimensions other than the first dimension;

counting data entries associated with one or more multi-dimensional data collections continuously arranged along each of the multiple dimensions;

identifying, based in part on the counted number of data entries for the one or more multi-dimensional data collections, a total number of data entries in the set of data entries, and a requested percentile, a relevant multi-dimensional data collection comprising a relevant data entry associated with the requested percentile; and

determining the percentile value to be one or more values between a lower bound, along the first dimension, of the relevant multi-dimensional data collection and a upper bound, along the first dimension, of the relevant multi-dimensional data collection.

10. The computer-readable media of claim 9, wherein the determining the percentile value comprises determining the percentile value to be an extrapolated value associated with the relevant data entry, the extrapolated value being based on the counted number of data entries for the relevant multi-dimensional data collection and on the lower bound, along the first dimension, of the relevant multi-dimensional data collection and the upper bound, along the first dimension, of the relevant multi-dimensional data collection.

11. The computer-readable media of claim 9, wherein the determining the percentile value comprises determining the percentile value to be a relevant data entry value associated with the relevant data entry, the relevant data entry being determined after sorting data entries within the relevant data collection according to their associated first dimension values.

12. The computer-readable media of claim 9, wherein the set of data entries is maintained in a relational database, and wherein further the counting is performed by an OLAP engine provided with a relational database application that manages the relational database.

13. A method for determining a percentile value of a set of data entries comprising the steps of:

dividing the data entries into buckets such that a first data entry, having a first dimension value, is divided into a first bucket, having a first bucket lower bound and a first bucket upper bound, both along a first dimension, if the first dimension value is between the first bucket lower bound and the first bucket upper bound;

defining multiple data collections continuously arranged along the first dimension such that a first data collection has a first data collection lower bound and a first data collection upper bound, both along the first dimension;

associating the first bucket with the first data collection if the first bucket lower bound and the first bucket upper bound are both between the first data collection lower bound and the first data collection upper bound;

counting the data entries divided into the buckets;

aggregating, for the multiple data collections, the counted number of data entries for buckets associated with the multiple data collections such that, if the first bucket is associated with the first data collection, then the counted number of data entries divided into the first bucket is also counted for the first data collection;

identifying, based in part on the aggregated number of data entries for the multiple data collections, a total number of data entries in the set of data entries, and a requested percentile, a relevant data collection comprising a relevant data entry, the relevant data entry associated with the requested percentile; and

determining the percentile value to be one or more values between a relevant data collection lower bound and a relevant data collection upper bound, both along the first dimension.

14. The method of claim 13, wherein the determining the percentile value comprises determining the percentile value to be an extrapolated value associated with the relevant data entry, the extrapolated value being based on the relevant data collection lower bound, the relevant data collection upper bound and an aggregated number of data entries within the relevant data collection.

15. The method of claim 13, wherein the determining the percentile value comprises determining the percentile value to be a relevant data entry value associated with the relevant data entry, the relevant data entry being determined after sorting data entries within the relevant data collection according to their associated first dimension values.

16. The method of claim 13, wherein the first data entry comprises additional dimension values;

the first bucket has a first bucket lower bound along each of the additional dimensions and a first bucket upper bound along each of the additional dimensions; and

the dividing the data entries into buckets further requires dividing the first data entry into the first bucket if the additional dimensional values are each between the first bucket lower bound along each respective additional dimension and the first bucket upper bound along each respective additional dimension.

17. The method of claim 13, wherein the defining the multiple data collections comprises selecting the first data collection lower bound along the first dimension and the first data collection upper bound along the first dimension such that values between the first data collection lower bound along the first dimension and the first data collection upper bound along the first dimension are comparable with respect to an analysis for which the percentile value is being determined.

18. The method of claim 13, wherein the set of data entries is maintained in a relational database, and wherein further the counting and the aggregating are performed by an OLAP engine provided with a relational database application that manages the relational database.

19. The method of claim 13 further comprising enabling selection of the requested percentile and enabling selection of one or more bounds along dimensions other than the first dimension, wherein the requested percentile is directed to values along the first dimension.

20. The method of claim 13, wherein the associating, counting, and aggregating are performed for each addition of one or more new data entries to the set of data entries.