Cube-based percentile calculation

• US 7,647,333 B2
• Filed: 06/21/2007
• Issued: 01/12/2010
• Est. Priority Date: 06/21/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Richard J, Chang, Chien-Shen
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Moser; Bruce M
• Application Number:
  US11/766,269
• Publication Number:
  US 20080320018A1
• Time in Patent Office: 936 Days
• Field of Search: 707/101
• 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 storage 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 and additional dimension values, is divided into a first bucket, having a first bucket lower bound and a first bucket upper bound, both along a first dimension and a first bucket lower bound and a first bucket upper bound, both along each of the additional dimensions, if the first dimension value is between the first bucket lower bound and the first bucket upper bound and 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;

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, an identified data collection comprising an identified data entry associated with the requested percentile; and

determining the percentile value to be a value between an identified data collection lower bound and an identified data collection upper bound, both along the first dimension.

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

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

4. The computer storage 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 a range of values between the first data collection lower bound along the first dimension and the first data collection upper bound along the first dimension is accurate given why the percentile value is being determined.

5. The computer storage 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.

6. The computer storage 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.

7. The computer storage 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.

8. One or more computer storage 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, an identified multi-dimensional data collection comprising an identified data entry associated with the requested percentile; and

determining the percentile value to be an extrapolated values being based on the counted number of data entries for the identified multi-dimensional data collection and on a lower bound, along the first dimension, of the identified multi-dimensional data collection and an upper bound, along the first dimension, of the identified multi-dimensional data collection.

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

utilizing a processing unit to divide the data entries into buckets such that a first data entry, having a first dimension value and additional dimension values, is divided into a first bucket, having a first bucket lower bound and a first bucket upper bound, both along a first dimension and a first bucket lower bound and a first bucket upper bound, both along each of the additional dimensions, if the first dimension value is between the first bucket lower bound and the first bucket upper bound and 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;

utilizing a processing unit to define 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;

utilizing a processing unit to associate 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;

utilizing a processing unit to count the data entries divided into the buckets;

utilizing a processing unit to aggregate, 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;

utilizing a processing unit to identify, 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, an identified data collection comprising an identified data entry, the identified data entry associated with the requested percentile; and

utilizing a processing unit to determine the percentile value to be a value between an identified data collection lower bound and an identified data collection upper bound, both along the first dimension.

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

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

12. The method of claim 9, 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 a range of values between the first data collection lower bound along the first dimension and the first data collection upper bound along the first dimension is accurate given why the percentile value is being determined.

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

14. The method of claim 9 further comprising utilizing a processing unit to enable selection of the requested percentile and enable 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.

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