Bounded Space Differentially Private Quantiles

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 polynomial in the input size $n$. In this work, we devise a differentially private algorithm for the quantile estimation problem with strongly sublinear space complexity. Our main mechanism estimates any $\alpha n$-approximate quantile of a length-$n$ stream over a data universe $\mathcal{X}$ with probability $1-\beta$ using $\tilde{O}\left( \frac{\log |\mathcal{X}| \log n}{\alpha \epsilon \beta}\right)$ space while satisfying $\epsilon$-differential privacy. Our mechanisms build upon the deterministic streaming algorithm of Greenwald and Khanna (2001) 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.