Accurate Quantile Estimation for Skewed Data Streams Using Nonlinear Interpolation

Quantile estimation is a fundamental method to generate the descriptions of the distribution of data for data management and analysis. Although the investigation and design of efficient quantile estimation algorithm has attracted much study, the problem of accurately finding quantiles in the case of skewed data streams, which are prevalent in many data sources like text data and IP traffic streams, is still not well addressed. In this paper, we specifically address the problem of estimating the quantiles of skewed data streams by designing and implementing an incremental quantile estimation with nonlinear-interpolation algorithm. The comprehensive experimental evaluation results demonstrate that the estimated quantiles of the proposed algorithm are more accurate than the existing methods in the literature on both synthetic and real-world datasets, especially on important extreme quantiles.