  Differential privacy is the de-facto privacy standard in data analysis. The
classic model of differential privacy considers the data to be static. The
dynamic setting, called differential privacy under continual observation,
captures many applications more realistically. In this work we consider several
natural dynamic data structure problems under continual observation, where we
want to maintain information about a changing data set such that we can answer
certain sets of queries at any given time while satisfying
$\epsilon$-differential privacy. The problems we consider include (a)
maintaining a histogram and various extensions of histogram queries such as
quantile queries, (b) maintaining a predecessor search data structure of a
dynamically changing set in a given ordered universe, and (c) maintaining the
cardinality of a dynamically changing set. For (a) we give new error bounds
parameterized in the maximum output of any query $c_{\max}$: our algorithm
gives an upper bound of $O(d\log^2dc_{\max}+\log T)$ for computing histogram,
the maximum and minimum column sum, quantiles on the column sums, and related
queries. The bound holds for unknown $c_{\max}$ and $T$. For (b), we give a
general reduction to orthogonal range counting. Further, we give an improvement
for the case where only insertions are allowed. We get a data structure which
for a given query, returns an interval that contains the predecessor, and at
most $O(\log^2 u \sqrt{\log T})$ more elements, where $u$ is the size of the
universe. The bound holds for unknown $T$. Lastly, for (c), we give a
parameterized upper bound of $O(\min(d,\sqrt{K\log T}))$, where $K$ is an upper
bound on the number of updates. We show a matching lower bound. Finally, we
show how to extend the bound for (c) for unknown $K$ and $T$.
