Simultaneous Approximation of Several Non-uniformly Distributed Values within Histogram Buckets

摘要

The problem of estimating median and other quantiles without storing observations was first proposed, in the field of simulation modeling to improve the studying of the performance of modeled systems rather than relying only on the mean and standard deviation alone. This problem is then extended to histogram plotting which raises the problem of estimating many quantiles of the same variable. However, the calculation of several values simultaneously is a computationally complex task since it requires several passes through the data. We propose in this paper an extension of the state-of the-art Values Approximation algorithm (Labbadi and Akichi, 2014) to estimate simultaneously several values within a histogram bucket. The extended algorithm significantly reduces the computation of the estimation since the original algorithm estimates only a single value. The experimental results show that the extended algorithm provides good estimates especially when data have non-equal spreads.