Streaming Quantiles Algorithms with Small Space and Update Time

Nikita Ivkin, Edo Liberty, Kevin J. Lang, Zohar S. Karnin, Vladimir Braverman

Introduction

In modern data processing, calculating exact quantiles—such as the median or the 99th percentile of network latency—is often impossible due to the sheer volume of data. Streaming algorithms address this by maintaining a "sketch," a compressed summary of the data. While the KLL algorithm is the theoretical state-of-the-art for these sketches, it faces practical challenges including high error constants and unpredictable latency spikes during updates. This paper introduces several enhancements to the KLL framework that significantly improve its real-world performance.

Methodology: Enhancing the KLL Framework

The authors propose several key modifications to improve memory efficiency and reduce error:

Lazy Compactions

In the standard KLL algorithm, each layer of the sketch has a fixed capacity. The authors introduce "lazy compactions," where all layers share a common memory pool. Compaction—the process of discarding half the data to save space—is only triggered when the entire pool is full. This approach allows for larger, more efficient compactions and maximizes memory utilization.

Memory utilization comparison: vanilla KLL vs. lazy KLL

Error Reduction and Spreading

Standard compactions discard items randomly, which can lead to "random walk" error accumulation. The authors implement Anti-Correlated Error Reduction by forcing a negative correlation between consecutive compactions, effectively canceling out much of the introduced error. Furthermore, they use Error Spreading, which randomly chooses between different compaction types to ensure that any specific query has an equal chance of being "inside" or "outside" a compacted range, thereby reducing variance.

Error analysis for a single query during a compaction

Sweep-Compactor

To address latency spikes, the authors replaced batch compactions with a "sweep" approach. This processes items incrementally, reducing the worst-case update time from $O(1/\epsilon)$ to $O(\log 1/\epsilon)$, which is critical for high-speed real-time systems.

Evaluation and Key Results

The algorithms were rigorously evaluated on synthetic data and real-world datasets, including CAIDA internet traffic traces and Wikimedia page view statistics.

  • Improved Accuracy: For the same memory footprint, the new techniques reduce the upper bound on sketch error by a factor of two.
  • Predictable Performance: The exponential improvement in worst-case update time makes the algorithm's performance much more predictable for high-speed streaming applications.
  • Weighted Streams: The paper also introduces extensions for weighted data, including a "weight-aware" compactor that handles items of varying weights directly.

Conclusion

This work demonstrates that even for theoretically optimal algorithms like KLL, there is significant room for practical improvement. By implementing "lazy" memory management and novel error-reduction techniques, the authors have created a more robust and accurate tool for quantile estimation in large-scale data streams. Future work may involve further empirical studies of wall-clock performance and exploring the mergeability of weight-aware compactors for distributed environments.

Summary updated

BibTeX
@misc{ivkin2019streaming,
  author = {Nikita Ivkin and Edo Liberty and Kevin J. Lang and Zohar S. Karnin and Vladimir Braverman},
  title = {{Streaming Quantiles Algorithms with Small Space and Update Time}},
  year = {2019},
  eprint = {1907.00236},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.00236},
}
Figure