Approximate Order Statistics Of Real Numbers In Generic Data

A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for computing an order statistic for a particular number in a set of numbers, the method comprising:

• determining an ordinality for each number in the set of numbers by performing a computation that is equivalent to,
• determining a representation for the number in scientific notation, wherein the representation includes as a mantissa and an exponent, and
• computing an ordinality for the number by subtracting from the exponent a count of significant digits (including significant zeros) in the mantissa that appear to the right of any decimal point in the mantissa;
• using the determined ordinality for each number to insert the number into a digest comprising one or more buckets, wherein each bucket is associated with an ordinality, a range of numerical values, and a count of the numbers contained in the bucket;
• and
• computing the order statistic for the particular number by performing computations involving counts for buckets in the digest.

An apparatus that computes an order statistic for a particular number in a set of numbers, comprising:

• a computing device comprising a processor and a memory, wherein the computing device is configured to:
• determine an ordinality for each number in the set of numbers by performing a computation that is equivalent to,
• determining a representation for the number in scientific notation, wherein the representation includes a mantissa and an exponent, and
• computing an ordinality for the number by subtracting from the exponent a count of significant digits (including significant zeros) in the mantissa that appear to the right of any decimal point in the mantissa;
• use the determined ordinality for each number to insert the number into a digest comprising one or more buckets, wherein each bucket is associated with a real number, a number of digits of precision, an ordinality, a range of numerical values, and a count of the numbers contained in the bucket, and wherein a given bucket in the digest includes all numbers that when truncated to the number of digits of precision equal the real number;
• and
• compute the order statistic for the particular number by performing computations involving counts for buckets in the digest.