Quantile estimation using the theory of stochastic learning

The goal of our research is to estimate the quantiles of a distribution from a large set of samples that arrive sequentially. Since the data set is large, the model we choose is that the data cannot be stored, but rather that estimates of the quantiles are computed in a real-time setting. In such settings, classical estimators that require storing the whole history of the data (or stream) cannot be deployed. In this paper, we present an incremental quantile estimator of a distribution, i.e., one that utilizes the previously-computed estimates and only resorts to the last sample for updating these estimates. The state-of-the-art work on obtaining incremental quantile estimators is due to Tierney [9], and is based on the theory of stochastic approximation. However, a primary shortcoming of the latter work is the requirement to incrementally build local approximations of the distribution function in the neighborhood of the quantiles. This requirement, unfortunately, increases the complexity of the algorithm. The convergence of the estimator suggested here is proven using the theory of stochastic learning. These theoretical results have been verified experimentally, and they demonstrate that our estimator outperforms the state-of-the-art estimators. In addition, it also copes with dynamic environments.