Patent ID: 8745109

Claim:
A method for calculating approximate order statistics from a collection of floating point numbers from a digest in a network comprising: accessing, by one or more processors, the digest wherein the digest is stored in a non-transitory memory, wherein: the digest includes a plurality of buckets positioned along a plurality of levels, each level is defined by an ordinality, each bucket of the plurality of buckets is defined by the ordinality of the level along which it is positioned, is further defined by a range limited by one or more extrema, and is associated with a count that reflects a quantity of floating point numbers having an ordinality matching the ordinality of the bucket, 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, the plurality of buckets includes a parent bucket that is positioned above a plurality of child buckets in a hierarchy in the digest, and the parent bucket has a non-zero count reflecting floating point numbers not reflected in the counts of the plurality of child buckets; receiving a query value; identifying, by the one or more processors, a set of buckets from amongst the plurality of buckets, such that either each bucket in the set of buckets is defined by a range below the query value or each bucket in the set of buckets is defined by a range above the query value; determining, by the one or more processors, a first count sum by summing the counts associated with the set of buckets; determining, by the one or more processors, a second count sum by summing the counts associated with the plurality of buckets; and estimating, by the one or more processors, an order statistic responsive to the query value based on the first count sum and the second count sum.