An ϵ-Approximation On-line Algorithm for Quantiles Based on Counters

The quantiles are very important as a statistic that gives an overview of big data. In this paper, we study the GK algorithm for finding $\epsilon$-approximate quantiles and point out its redundancy hidden the quantile summary. We introduce a counter mechanism and give a new approximation algorithm that is more space efficient. We theoretically guarantee that the maximum quantile error is within the range of the $\epsilon$-approximation, and confirm by computational experiments that the spatial complexity required to preserve the $\epsilon$-approximate quantile summary is significantly improved.