Approximate order statistics of real numbers in generic data

• US 8,756,262 B2
• Filed: 03/01/2011
• Issued: 06/17/2014
• Est. Priority Date: 03/01/2011
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Zhang, Steve Yu
• Primary Examiner(s): Ngo, Chuong D
• Assistant Examiner(s): Hughes, Kevin G
• Application Number:
  US13/038,085
• Publication Number:
  US 20120226723A1
• Time in Patent Office: 1,204 Days
• Field of Search: 708/200
• US Class Current: 708/200
• 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 computer-implemented method for calculating approximate order statistics from a collection of floating point numbers from a digest in a network comprising:

receiving machine data, wherein the machine data includes a floating point number;

extracting, using one or more processors, the floating point number from the machine data;

determining, using the one or more processors, an ordinality of the floating point number, wherein the ordinality of each floating point number is determined by converting the floating point number to a mantissa and an exponent and subtracting a number of significant digits in the mantissa to the right of the decimal point including significant zeros from the exponent;

identifying, using the one or more processors and based on the determined ordinality, a level from amongst a plurality of levels in the digest, the digest being stored in a non-transitory memory and including a plurality of buckets positioned along the plurality of levels, wherein each bucket of the plurality of buckets is;

defined by the ordinality of the level along which it is positioned,

further defined by a range limited by one or more extrema, and

associated with a count that reflects a quantity of floating point numbers;

identifying, using the one or more processors, a bucket positioned at the identified level and being defined by a range that is inclusive of the floating point number;

incrementing, using the one or more processors, the count of the identified bucket, wherein the identified bucket, for which the count was incremented, has a plurality of child buckets in the digest, wherein the digest is configured to be used to generate a response to a query based on the incremented count of the bucket;

identifying, using the one or more processors, a set of buckets based on a query value in the query, wherein the set of buckets includes the identified bucket; and

estimating, using the one or more processors, an order statistic for the query value based on a summation of counts associated with the identified set of buckets.

2. The method of claim 1, wherein a first sum of the counts across all buckets in a first level of the plurality of levels is not equal to a second sum of the counts in a second level of the plurality of levels.

3. The method of claim 1, wherein the range of each bucket of the plurality of buckets is implicitly defined based on a precision of a number.

4. The method of claim 1, wherein identifying the bucket comprises identifying a bucket within the level being defined by a number that matches the floating point number.

5. The method of claim 1, further comprising:

merging the digest with another digest.

6. The method of claim 1, further comprising:

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 floating point numbers added to the digest divided by a constant.

7. The method of claim 6, 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;

receiving machine data, wherein the machine data includes a floating point number;

extracting the floating point number from the machine data;

determining an ordinality of the floating point number, wherein the ordinality of each floating point number is determined by converting the floating point number to a mantissa and an exponent and subtracting a number of significant digits in the mantissa to the right of the decimal point including significant zeros from the exponent;

identifying, based on the determined ordinality, a level from amongst a plurality of levels in the digest, the digest being stored in a non-transitory memory and including a plurality of buckets positioned along the plurality of levels, wherein each bucket of the plurality of buckets is;

defined by the ordinality of the level along which it is positioned,

further defined by a range limited by one or more extrema, and

associated with a count that reflects a quantity of floating point numbers;

identifying a bucket positioned at the identified level and being defined by a range that is inclusive of the floating point number;

incrementing the count of the identified bucket, wherein the identified bucket, for which the count was incremented, has a plurality of child buckets in the digest, wherein the digest is configured to be used to generate a response to a query based on the incremented count of the bucket;

identifying a set of buckets based on a query value in the query, wherein the set of buckets includes the identified bucket; and

estimating an order statistic for the query value based on a summation of counts associated with the identified set of buckets.

9. The apparatus of claim 8, wherein a first sum of the counts across all buckets in a first level of the plurality of levels is not equal to a second sum of the counts in a second level of the plurality of levels.

10. The apparatus of claim 8, wherein the range of each bucket of the plurality of buckets is implicitly defined based on a precision of a number.

11. The apparatus of claim 8, wherein identifying the bucket comprises identifying a bucket within the level being defined by a number that matches the floating point number.

12. The apparatus of claim 8, further comprising:

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 floating point numbers added to the digest divided by a constant.

13. The apparatus of claim 12, 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:

accessing a set of floating point numbers

receiving machine data, wherein the machine data includes a floating point number;

extracting the floating point number from the machine data;

determining an ordinality of the floating point number, wherein the ordinality of each floating point number is determined by converting the floating point number to a mantissa and an exponent and subtracting a number of significant digits in the mantissa to the right of the decimal point including significant zeros from the exponent;

identifying, based on the determined ordinality, a level from amongst a plurality of levels in the digest, the digest being stored in a non-transitory memory and including a plurality of buckets positioned along the plurality of levels, wherein each bucket of the plurality of buckets is;

defined by the ordinality of the level along which it is positioned,

further defined by a range limited by one or more extrema, and

associated with a count that reflects a quantity of floating point numbers;

identifying a bucket positioned at the identified level and being defined by a range that is inclusive of the floating point number;

incrementing the count of the identified bucket, wherein the identified bucket, for which the count was incremented, has a plurality of child buckets in the digest, wherein the digest is configured to be used to generate a response to a query based on the incremented count of the bucket;

identifying a set of buckets based on a query value in the query, wherein the set of buckets includes the identified bucket; and

estimating an order statistic for the query value based on a summation of counts associated with the identified set of buckets.

15. The processor readable storage medium of claim 14, wherein a first sum of the counts across all buckets in a first level of the plurality of levels is not equal to a second sum of the counts in a second level of the plurality of levels.

16. The processor readable storage medium of claim 14, wherein the range of each bucket of the plurality of buckets is implicitly defined based on a precision of a number.

17. The processor readable storage medium of claim 14, wherein identifying the bucket comprises identifying a bucket within the level being defined by a number that matches the floating point number.

18. 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.

19. The processor readable storage medium of claim 14, wherein the memory contains instructions further causing the processor to:

compress 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 floating point numbers added to the digest divided by a constant.

20. The processor readable storage medium of claim 19, 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 digest derived from a collection of floating point numbers, wherein the digest includes one or more buckets grouped into one or more levels, wherein a bucket is created for a floating point number the digest lacks a bucket defined by an ordinality matching an ordinality of the number and further defined by a range inclusive of the floating point number and wherein the ordinality of each floating point number is determined by converting the floating point number to a mantissa and an exponent and subtracting a number of significant digits in the mantissa to the right of the decimal point including significant zeros from the exponent, wherein the created bucket is added to a level associated with the ordinality of the floating point number, and wherein the direst is configured to be used to generate a response to a query based on a count of the created bucket; and

a second computing device configured to perform actions comprising;

receiving the digest;

identifying a set of buckets based on a query value in the query; and

estimating an order statistic for the query value based on a summation of counts associated with the identified set of buckets.

22. The system of claim 21, wherein the bucket is associated with a count that reflects a quantity of floating point numbers having an ordinality matching an ordinality defining the bucket and having a value within the range defined for the bucket.