Patent Document ID: 9760605
Application ID: 14481211
Patent Status: 1

Claim One:
1. A method for precise quantile determination comprising: receiving, by a processor, datapoints and one or more quantiles to be computed; determining, by the processor, from the datapoints and the one or more quantiles to be computed, a maximum relative error value e so that a rank distance between two adjacent elements in all of the one or more quantiles is at most 2ε, wherein the maximum relative error value ε guarantees that an exact result for every quantile is determined in no more than two passes; computing, by the processor, in a first pass of the datapoints using an approximation algorithm and the maximum relative error value ε, a quantile summary of the datapoints that specifies lower and upper bounds of the quantile ranks for selected datapoints; determining, by the processor, for each quantile rank, the lower and upper bounds for values between which the quantile must occur; filtering out, by the processor, in a second pass over the datapoints those datapoints that are not between the lower and upper bounds to provide subsets within the lower and upper bounds; and computing, by the processor, from the quantile ranks and the subsets which were provided by the filtering out within the lower and upper bounds which were specified using the maximum relative error value ε, the precise quantiles.