  In this work, we study the task of estimating the numbers of distinct and
$k$-occurring items in a time window under the constraint of differential
privacy (DP). We consider several variants depending on whether the queries are
on general time windows (between times $t_1$ and $t_2$), or are restricted to
being cumulative (between times $1$ and $t_2$), and depending on whether the DP
neighboring relation is event-level or the more stringent item-level. We obtain
nearly tight upper and lower bounds on the errors of DP algorithms for these
problems. En route, we obtain an event-level DP algorithm for estimating, at
each time step, the number of distinct items seen over the last $W$ updates
with error polylogarithmic in $W$; this answers an open question of Bolot et
al. (ICDT 2013).
