Tracking of Multiple Quantiles in Dynamically Varying Data Streams

Abstract

In this paper we consider the problem of tracking multiple quantiles of dynamicallyvarying data stream distributions. The method is based on making incremental updates ofthe quantile estimates every time a new sample is received. The method is memory andcomputationally efficient since it only stores one value for each quantile estimate and onlyperforms one operation per quantile estimate when a new sample is received from the datastream. The estimates are realistic in the sense that the monotone property of quantiles issatisfied in every iteration. Experiments show that the method efficiently tracks multiplequantiles and outperforms state of the art methods.