A Fast Algorithm for Approximate Quantiles in High Speed Data Streams

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 and the stream is partitioned into sub-streams of exponentially increasing size as they arrive.

Abstract

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 ɛ log ɛN)) and an average per-element update cost of O(log log N) if ɛ is fixed. 1