Incremental Quantiles Estimators for Tracking Multiple Quantiles

Abstract

In this paper, we investigate the problem of estimating multiple quantiles when samples are received online (data stream). We assume that we are dealing with a dynamical system, i.e. the distribution of the samples from the data stream changes with time. A major challenge arises when simultaneously maintaining multiple quantile estimates using incremental type of estimators. In fact, a naive implementation where multiple incremental quantile estimators are updated in isolation might lead to violation monotone property of quantiles, i.e., an estimate of a lower target quantile might erroneously overpass that of a higher one. Surprisingly, the related work on countering those violations is extremely sparse [1, 3] and almost absent.

Our work tries to fill this literature gap by proposing two solutions to the problem that build on the deterministic update based multiplicative incremental quantile estimator (DUMIQE) recently proposed by Yazidi and Hammer [5], which was shown to be the most efficient incremental quantile estimator in the literature.

Experimental results show that the modified DUMIQE methods perform very well and have a superior performance to the DUMIQE. Moreover, our proposed methods satisfy the monotone property of quantiles. The methods outperform the state of the art multiple incremental quantile estimator of Cao et al. [1, 3].