  There are now several large scale deployments of differential privacy used to
collect statistical information about users. However, these deployments
periodically recollect the data and recompute the statistics using algorithms
designed for a single use. As a result, these systems do not provide meaningful
privacy guarantees over long time scales. Moreover, existing techniques to
mitigate this effect do not apply in the "local model" of differential privacy
that these systems use.
  In this paper, we introduce a new technique for local differential privacy
that makes it possible to maintain up-to-date statistics over time, with
privacy guarantees that degrade only in the number of changes in the underlying
distribution rather than the number of collection periods. We use our technique
for tracking a changing statistic in the setting where users are partitioned
into an unknown collection of groups, and at every time period each user draws
a single bit from a common (but changing) group-specific distribution. We also
provide an application to frequency and heavy-hitter estimation.
