  We define a new interactive differentially private mechanism -- the median
mechanism -- for answering arbitrary predicate queries that arrive online.
Relative to fixed accuracy and privacy constraints, this mechanism can answer
exponentially more queries than the previously best known interactive privacy
mechanism (the Laplace mechanism, which independently perturbs each query
result). Our guarantee is almost the best possible, even for non-interactive
privacy mechanisms. Conceptually, the median mechanism is the first privacy
mechanism capable of identifying and exploiting correlations among queries in
an interactive setting.
  We also give an efficient implementation of the median mechanism, with
running time polynomial in the number of queries, the database size, and the
domain size. This efficient implementation guarantees privacy for all input
databases, and accurate query results for almost all input databases. The
dependence of the privacy on the number of queries in this mechanism improves
over that of the best previously known efficient mechanism by a
super-polynomial factor, even in the non-interactive setting.
