Differentially Private Quantiles
  Quantiles are often used for summarizing and understanding data. If that data
is sensitive, it may be necessary to compute quantiles in a way that is
differentially private, providing theoretical guarantees that the result does
not reveal private information. However, when multiple quantiles are needed,
existing differentially private algorithms fare poorly: they either compute
quantiles individually, splitting the privacy budget, or summarize the entire
distribution, wasting effort. In either case the result is reduced accuracy. In
this work we propose an instance of the exponential mechanism that
simultaneously estimates exactly $m$ quantiles from $n$ data points while
guaranteeing differential privacy. The utility function is carefully structured
to allow for an efficient implementation that returns estimates of all $m$
quantiles in time $O(mn\log(n) + m^2n)$. Experiments show that our method
significantly outperforms the current state of the art on both real and
synthetic data while remaining efficient enough to be practical.
