# Bounded Space Differentially Private Quantiles

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2022.

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

- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [Efficient Federated Conformal Prediction with Group-Conditional Guarantee](https://mlsanity.com/paper/2603.14198/) (2026)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Differentially Private Online Bayesian Estimation With Adaptive Truncation](https://mlsanity.com/paper/2301.08202/) (2023)
- [Federated Computation of ROC and PR Curves](https://mlsanity.com/paper/2510.04979/) (2025)

## Abstract (arXiv)

Estimating the quantiles of a large dataset is a fundamental problem in both the streaming algorithms literature and the differential privacy literature. However, all existing private mechanisms for distribution-independent quantile computation require space at least linear in the input size n. In this work, we devise a differentially private algorithm for the quantile estimation problem, with strongly sublinear space complexity, in the one-shot and continual observation settings. Our basic mechanism estimates any α-approximate quantile of a length-n stream over a data universe X with probability 1-β using Oleft( fraclog (|X|/β) log (α ε n)α ε right) space while satisfying ε-differential privacy at a single time point. Our approach builds upon deterministic streaming algorithms for non-private quantile estimation instantiating the exponential mechanism using a utility function defined on sketch items, while (privately) sampling from intervals defined by the sketch. We also present another algorithm based on histograms that is especially suited to the multiple quantiles case. We implement our algorithms and experimentally evaluate them on synthetic and real-world datasets.