LDP-IDS: Local Differential Privacy for Infinite Data Streams

Streaming data collection is essential to real-time data analytics in various IoTs and mobile device-based systems, which, however, may expose end users' privacy. Local differential privacy (LDP) is a promising solution to privacy-preserving data collection and analysis. However, existing few LDP studies over streams are either applicable to finite streams only or suffering from great utility loss due to simply adopting the budget division method in centralized differential privacy. In this paper, we study this problem by first proposing LDP-IDS, a novel LDP paradigm for infinite streams, and designing baseline approaches under the budget division framework. Particularly, we develop two budget division methods that are adaptive to sparsity changes in streams, with better data utility and communication efficiency. To improve the poor utility in budget division-based LDP, we then propose a population division framework that can not only avoid the high sensitivity of LDP noise to the budget division but also require significantly less communication. Under the population division framework, we also present two data-adaptive methods with theoretical analysis to further improve the estimation accuracy by leveraging the sparsity of data streams. We conduct extensive experiments on synthetic and real-world datasets to evaluate the effectiveness of utility of LDP-IDS. Experimental results demonstrate that, compared to the budget division-based solutions, our population division-based and data-adaptive algorithms for LDP-IDS can significantly reduce the utility loss and communication cost.