APPROXIMATE ORDER STATISTICS OF REAL NUMBERS IN GENERIC DATA

• US 20120226723A1
• Filed: 03/01/2011
• Published: 09/06/2012
• Est. Priority Date: 03/01/2011
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Zhang, Steve Yu
• Granted Patent: US 8,756,262 B2
• Time in Patent Office: Days
• US Class Current: 708/203
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence

Abstract

A method, system, and processor-readable storage medium are directed towards calculating approximate order statistics on a collection of real numbers. In one embodiment, the collection of real numbers is processed to create a digest comprising hierarchy of buckets. Each bucket is assigned a real number N having P digits of precision and ordinality O. The hierarchy is defined by grouping buckets into levels, where each level contains all buckets of a given ordinality. Each individual bucket in the hierarchy defines a range of numbers—all numbers that, after being truncated to that bucket'"'"'s P digits of precision, are equal to that bucket'"'"'s N. Each bucket additionally maintains a count of how many numbers have fallen within that bucket'"'"'s range. Approximate order statistics may then be calculated by traversing the hierarchy and performing an operation on some or all of the ranges and counts associated with each bucket.

Claims

1. A method for calculating approximate order statistics from a collection of real numbers comprising:

inserting at least one of the collection of real numbers into a digest stored in a non-transitory memory, wherein the digest includes one or more buckets grouped into one or more levels, wherein a bucket is created for a real number upon insertion into the digest, and wherein the created bucket is added to a level associated with an ordinality of the inserted real number.

compressing the digest by collapsing a bucket, at least one of the bucket'"'"'s siblings, and the bucket'"'"'s parent into the bucket'"'"'s parent when a sum of the counts of the bucket, at least one of the bucket'"'"'s siblings, and the bucket'"'"'s parent is less than a number of real numbers added to the digest divided by a constant; and

calculating an approximate order statistic for a query value by summing all of the counts of all buckets in the digest having a value less than the query value.

2. The method of claim 1, wherein the collection of real numbers includes a plurality of untyped strings.

3. The method of claim 1, wherein a bucket is associated with a range defined by all numbers that, when truncated to the number of digits of precision of a number associated with the bucket, equals the number associated with the bucket.

4. The method of claim 1, wherein the count associated with a bucket is incremented when the real number inserted into the digest matches a number associated with the bucket.

5. The method of claim 1, wherein ordinality of a number is calculated by:

converting the number to scientific notation having a mantissa and an exponent; and

adding the negative of the number of digits in the mantissa to the right of the decimal point with the exponent.

6. The method of claim 1, further comprising:

merging the digest with another digest.

7. The method of claim 1, wherein collapsing the bucket, the at least one bucket'"'"'s siblings, and the bucket'"'"'s parent includes assigning the sum of the counts of the bucket, the bucket'"'"'s siblings, and the bucket'"'"'s parent to the count of the bucket'"'"'s parent, and deleting each of the bucket and the bucket'"'"'s siblings.

8. An apparatus for calculating approximate order statistics, comprising:

a processor; and

a memory storing instructions that when executed by the processor cause actions to be performed, including;

inserting at least one of the collection of real numbers into a digest, wherein the digest includes one or more buckets grouped into one or more levels, wherein a bucket is created for a real number upon insertion into the digest, and wherein the created bucket is added to a level associated with an ordinality of the inserted real number.

compressing the digest by collapsing a bucket, at least one of the bucket'"'"'s siblings, and the bucket'"'"'s parent into the bucket'"'"'s parent when a sum of the counts of the bucket, at least one of the bucket'"'"'s siblings, and the bucket'"'"'s parent is less than a number of real numbers added to the digest divided by a constant; and

calculating an approximate order statistic for a query value by summing all of the counts of all buckets in the digest having a value less than the query value.

9. The apparatus of claim 8, wherein the collection of real numbers includes a plurality of untyped strings.

10. The apparatus of claim 8, wherein a bucket is associated with a range defined by all numbers that, when truncated to the number of digits of precision of a number associated with the bucket, equals the number associated with the bucket.

11. The apparatus of claim 8, wherein the count associated with a bucket is incremented when the real number inserted into the digest matches a number associated with the bucket.

12. The apparatus of claim 8, wherein ordinality of a number is calculated by:

converting the number to scientific notation having a mantissa and an exponent; and

adding the negative of the number of digits in the mantissa to the right of the decimal point with the exponent.

13. The apparatus of claim 8, wherein collapsing the bucket, the at:

least, one bucket'"'"'s siblings, and the bucket'"'"'s parent includes assigning the sum of the counts of the bucket, the bucket'"'"'s siblings, and the bucket'"'"'s parent to the count of the bucket'"'"'s parent, and deleting each of the bucket and the bucket'"'"'s siblings.

14. A non-transitory processor readable storage medium storing instructions that cause a processor to perform actions, comprising:

inserting at least one of the collection of real numbers into a digest, wherein the digest includes one or more buckets grouped into one or more levels, wherein a bucket is created for a real number upon insertion into the digest, and wherein the created bucket is added to a level associated with an ordinality of the inserted real number.

compressing the digest by collapsing a bucket, at least one of the bucket'"'"'s siblings, and the bucket'"'"'s parent into the bucket'"'"'s parent when a sum of the counts of the bucket, at least one of the bucket'"'"'s siblings, and the bucket'"'"'s parent is less than a number of real numbers added to the digest divided by a constant; and

calculating an approximate order statistic for a query value by summing all of the counts of all buckets in the digest having a value less than the query value.

15. The processor readable storage medium of claim 14, wherein the collection of real numbers includes a plurality of untyped strings.

16. The processor readable storage medium of claim 14, wherein a bucket is associated with a range defined by all numbers that, when truncated to the number of digits of precision of a number associated with the bucket, equals the number associated with the bucket.

17. The processor readable storage medium of claim 16, wherein the count associated with a bucket is incremented when the real number inserted into the digest matches a number associated with the bucket.

18. The processor readable storage medium of claim 14, wherein the memory contains instructions further causing the processor to calculate ordinality by:

converting the number to scientific notation having a mantissa and an exponent; and

adding the negative of the number of digits in the mantissa to the right of the decimal point with the exponent.

19. The processor readable storage medium of claim 14, the memory contains instructions further causing the processor to perform actions comprising;

merging the digest with another digest.

20. The processor readable storage medium of claim 14, wherein collapsing the bucket, the at least one bucket'"'"'s siblings, and the bucket'"'"'s parent includes assigning the sum of the counts of the bucket, the bucket'"'"'s siblings, and the bucket'"'"'s parent to the count of the bucket'"'"'s parent, and deleting each of the bucket and the bucket'"'"'s siblings.

21. A system comprising:

a first computing device storing a first digest derived from a first collection of real numbers;

a second computing device storing a second digest derived from a second collection of real numbers, wherein the first digest and the second digest each include one or more buckets grouped into one or more levels, wherein a bucket is created for a real number the first time that real number is added to the digest, and wherein the created bucket is added to a level associated with an ordinality of the inserted real number; and

a third computing device configured to perform actions comprising;

receiving the first digest and the second digest;

merging the first digest and the second digest into a merged digest; and

calculating an approximate order statistic for a query value by summing all of the counts of all buckets in the merged digest having a value less than the query value.

22. The system of claim 21, wherein the insertion of a real number when a bucket has already been created for that real number are performed by incrementing the count of the bucket that has already been created for that real number.