Patent Document ID: 9268796
Application ID: 13482095
Patent Status: 1

Claim One:
1. A computer-implemented method for estimating quantiles for data stored in a distributed system, comprising: receiving an instruction to estimate a specified quantile for a variate in a set of data stored at a plurality of nodes in the distributed system; identifying a minimum data value and a maximum data value for the variate from the set of data; defining a plurality of data bins for the variate, wherein the plurality of data bins collectively range from the minimum data value to the maximum data value and each of the plurality of data bins is associated with a different range of data values in the set of data; determining a total number of data values in the set of data that fall within each of the plurality of data bins; determining lower and upper quantile bounds for each of the plurality of data bins based at least in part on the total number of data values that fall within each of the plurality of data bins; identifying one of the plurality of data bins that includes the specified quantile based on the lower and upper quantile bounds; estimating the specified quantile based on the identified one of the plurality of data bins; and storing data including the estimated specified quantile and the upper and lower quantile bounds, wherein when another plurality of data bins is defined, the stored data is used to narrow one or more spans of lower and upper quantile bounds of the another plurality of data bins; wherein the operations of the method are performed by one or more hardware processors in the distributed system.