| 主权项 |
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 s that 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 ε, 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 within the lower and upper bounds, the precise quantiles. |
