Single pass space efficent system and method for generating approximate quantiles satisfying an apriori user-defined approximation error

摘要

A system and method for finding an epsilon -approximate phi -quantile data element of a data set with N data elements in a single pass over the data set. The epsilon -approximate phi -quantile data element is guaranteed to lie within a user-specified approximation error epsilon of a true phi -quantile data element being sought. B buffers, each having a capacity of k elements, initially are filled with sorted data elements from the data set, with the values of b and k depending on epsilon and N. The buffers are then collapsed into an output buffer, with the remaining buffers then being refilled with data elements, collapsed (along with the previous output buffer), and so on until the entire data set has been processed and a single output buffer remains. A data element of the output buffer corresponding to the epsilon -approximate phi -quantile is then output as the approximate phi -quantile data element. If desired, the system and method can be practiced with sampling to even further reduce the amount of space required to find a desired epsilon -approximate phi -quantile data element.