A Fast Algorithm for Approximate Quantiles in High Speed Data Streams
Qi Zhang, Wei Wang · International Conference on Scientific and Statistical Database Management · 2007
We present a fast algorithm for computing approximate quantiles in high speed data streams with deterministic error bounds. For data streams of size N where N is unknown in advance, our algorithm partitions the stream into sub-streams of exponentially increasing size as they arrive. For each sub-stream which has a fixed size, we compute and maintain a multi-level summary structure using a novel algorithm. In order to achieve high speed performance, the algorithm uses simple block-wise merge and sample operations. Overall, our algorithms for fixed-size streams and arbitrary-size streams have a computational cost of O(N log(1/epsivlogepsivN)) and an average per-element update cost of O(log logN) if epsiv is fixed.
Cited by 47 works. doi:10.1109/ssdbm.2007.27
Authors
References
- Space-efficient online computation of quantile summaries
- Approximate medians and other quantiles in one pass and with limited memory
- The P 2 algorithm for dynamic calculation of quantiles and histograms without storing observations
- Selection and sorting with limited storage
- Random sampling techniques for space efficient online computation of order statistics of large datasets
- Medians and beyond
- A One-Pass Space-Efficient Algorithm for Finding Quantiles.
- Approximate medians and other quantiles in one pass and with limited memory
- Progress in selection
- Approximate counts and quantiles over sliding windows