# Optimal Quantile Approximation in Streams

arXiv: https://arxiv.org/abs/1603.05346 · HTML: https://mlsanity.com/paper/1603.05346/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2016.

## Built on by (most cited first, 12 of 12)

- [Amazon SageMaker Model Monitor: A System for Real-Time Insights into Deployed Machine Learning Models](https://mlsanity.com/paper/2111.13657/) (2021)
- [FedXGBoost: Privacy-Preserving XGBoost for Federated Learning](https://mlsanity.com/paper/2106.10662/) (2021)
- [A Human-Centric Take on Model Monitoring](https://mlsanity.com/paper/2206.02868/) (2022)
- [Leveraging the Christoffel Function for Outlier Detection in Data Streams](https://mlsanity.com/paper/2508.16617/) (2025)
- [Non-Stochastic CDF Estimation Using Threshold Queries](https://mlsanity.com/paper/2301.05682/) (2023)
- [Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees](https://mlsanity.com/paper/2304.07652/) (2023)
- [Adapting to Covariate Shift in Real-time by Encoding Trees with Motion Equations](https://mlsanity.com/paper/2404.05168/) (2024)
- [Federated Learning for Collaborative Inference Systems: The Case of Early Exit Networks](https://mlsanity.com/paper/2405.04249/) (2024)
- [Streaming Sliced Optimal Transport](https://mlsanity.com/paper/2505.06835/) (2025)
- [FedPS: Federated Preprocessing for structured data via aggregated Statistics](https://mlsanity.com/paper/2602.10870/) (2026)
- [Federated Measurement of Demographic Disparities from Quantile Sketches](https://mlsanity.com/paper/2602.18870/) (2026)
- [MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound](https://mlsanity.com/paper/2605.11617/) (2026)

## Abstract (arXiv)

This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An varepsilon approximate quantile sketch receives a stream of items x1,ldots,xn and allows one to approximate the rank of any query up to additive error varepsilon n with probability at least 1-δ. The rank of a query x is the number of stream items such that xi ≤ x. The minimal sketch size required for this task is trivially at least 1/varepsilon. Felber and Ostrovsky obtain a O((1/varepsilon)log(1/varepsilon)) space sketch for a fixed δ. To date, no better upper or lower bounds were known even for randomly permuted streams or for approximating a specific quantile, e.g., the median. This paper obtains an O((1/varepsilon)log log (1/δ)) space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This subtle modification allows for an analysis which is both tight and extremely simple. Similar techniques should be useful for improving other sketching objectives and geometric coreset constructions.