Differentially Private Approximate Quantiles
This work addresses the challenge of preserving privacy while accurately estimating quantiles, which is crucial for data analysis in sensitive domains, representing a strong specific gain.
The authors tackled the problem of computing differentially private quantiles with high accuracy and efficiency, achieving significantly lower error and running two orders of magnitude faster than previous methods.
In this work we study the problem of differentially private (DP) quantiles, in which given dataset $X$ and quantiles $q_1, ..., q_m \in [0,1]$, we want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call ApproximateQuantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.