Smooth estimates of multiple quantiles in dynamically varying data streams
Journal article, Peer reviewed
MetadataShow full item record
Original versionHammer HL, Yazidi A. Smooth estimates of multiple quantiles in dynamically varying data streams. Pattern Analysis and Applications . 2019 https://dx.doi.org/10.1007/s10044-019-00794-3
In this paper, we investigate the problem of estimating multiple quantiles when samples are received online (data stream). We assume a dynamical system, i.e. the distribution of the samples from the data stream changes with time. A major challenge of using incremental quantile estimators to track multiple quantiles is that we are not guaranteed that the monotone property of quantiles will be satisﬁed, i.e, an estimate of a lower quantile might erroneously overpass that of a higher quantile estimate. Surprisingly, we have only found two papers in the literature that attempt to counter these challenges, namely the works of Cao et al.  and Hammer and Yazidi  where the latter is a preliminary version of the work in this paper. Furthermore, the state-of-the-art incremental quantile estimator called Deterministic Update based Multiplicative Incremental Quantile Estimator (DUMIQE), due to Yazidi and Hammer , fails to guarantee the monotone property when estimating multiple quantiles. A challenge with the solutions in  and , is that even though the estimates satisfy the monotone property of quantiles, the estimates can be highly irregular relative to each other which usually is unrealistic from a practical point of view. In this paper we suggest to generate the quantile estimates by inserting the quantile probabilities (e.g. 0.1,0.2,...,0.9) into a monotonically increasing and inﬁnitely smooth function (can be diﬀerentiated inﬁnitely many times). The function is incrementally updated from the data stream. The monotonicity and smoothness of the function ensure that both the monotone property and regularity requirement of the quantile estimates are satisﬁed. The experimental results show that the method perform very well and estimate multiple quantiles more precisely than the original DUMIQE  and the approaches reported in  and .