Local Differentially Private Release of Infinite Streams With Temporal Relevance

The data stream generated by users on web applications is often collected using a local differential privacy (LDP) approach to ensure privacy. This approach offers rigorous theoretical guarantees and low computational overhead, albeit at the expense of data utility. Data utility encompasses both the value of individual data points and the temporal relevance that exists between them, but existing studies primarily focus on enhancing the former utility while neglecting the latter. Furthermore, the collected data often requires cleaning, and we have demonstrated through a case study that data stream lacking time relevance poses a significant risk to users' privacy during the cleaning process. In this paper, for the first time we present an online LDP publishing mechanism while preserving the inherent temporal relevance for the infinite stream, called the Sampling Period Perturbation Algorithm (SPPA). Specifically, we model the temporal relevance between data points as the Fourier interpolation function, resulting in a computational complexity reduction from O(n2) to O(n log n) when compared with the conventional Markov approach in the offline setting. To strike a better balance between privacy and utility, we add noise to the sampling period due to its minimal impact on sensitivity, which is analyzed by our novel concepts of (ε,τ)-temporal indistinguishability and (ε,w,τ)-event LDP. Through extensive experiments, SPPA exhibits superior performance in terms of both data utility and privacy preservation compared to the state-of-the-art baselines. In particular, when ε=1, compared with the state-of-the-art baseline, SPPA diminishes the MSE by up to 64.2%, and raises the event monitoring efficiency by up to 21.4%.