Online Algorithm for Approximate Quantile Queries on Sliding Windows

We address the problem of estimating statistical information about the most recent parts of a stream of incoming data. In particular, we provide an improved algorithm for estimating approximate quantiles in the ``sliding window'' model of streams. We extend the GK algorithm by replacing its numeric counters with a sliding-window sketch based on the exponential histograms (EH) technique. By analyzing the GK algorithm and using a sliding window sketch which performs only the necessary operations, we achieve improved runtime performance on real-world data sets compared to previous sliding window algorithms for quantile estimation.