A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data
Khaled A. Alsabti, Sanjay Ranka, Vineet Kumar Singh · Syracuse University Libraries (Syracuse University) · 1997
The '-quantile of an ordered sequence of data values is the element with rank 'n, where n is the total number of values. Accurate estimates of quantiles are required for the solution of many practical problems. In this paper, we present a new algorithm for estimating the quantile values for disk-resident data. Our algorithm has the following characteristics: (1) It requires only one pass over the data; (2) It is deterministic; (3) It produces good lower and upper bounds of the true values of the quantiles; (4) It requires no a priori knowledge of the distribution of the data set; (5) It has a scalable parallel formulation; (6) Extra time and memory for computing additional quantiles (beyond the first one) are constant per quantile. We present experimental results on the IBM SP-2. The experimental results show that the algorithm is indeed robust and does not depend on the distribution of the data sets. 1 Introduction The '-quantile of an ordered sequence of data values is the element...