  Collecting and analyzing evolving longitudinal data has become a common
practice. One possible approach to protect the users' privacy in this context
is to use local differential privacy (LDP) protocols, which ensure the privacy
protection of all users even in the case of a breach or data misuse. Existing
LDP data collection protocols such as Google's RAPPOR and Microsoft's
dBitFlipPM can have longitudinal privacy linear to the domain size k, which is
excessive for large domains, such as Internet domains. To solve this issue, in
this paper we introduce a new LDP data collection protocol for longitudinal
frequency monitoring named LOngitudinal LOcal HAshing (LOLOHA) with formal
privacy guarantees. In addition, the privacy-utility trade-off of our protocol
is only linear with respect to a reduced domain size $2\leq g \ll k$. LOLOHA
combines a domain reduction approach via local hashing with double
randomization to minimize the privacy leakage incurred by data updates. As
demonstrated by our theoretical analysis as well as our experimental
evaluation, LOLOHA achieves a utility competitive to current state-of-the-art
protocols, while substantially minimizing the longitudinal privacy budget
consumption by up to k/g orders of magnitude.
