Towards Pattern-aware Privacy-preserving Real-time Data Collection

摘要

Although time-series data collected from users can be utilized to provide services for various applications, they could reveal sensitive information about users. Recently, local differential privacy (LDP) has emerged as the state-of-art approach to protect data privacy by perturbing data locally before outsourcing. However, existing works based on LDP perturb each data point separately without considering the correlations between consecutive data points in time-series. Thus, the important patterns of each time-series might be distorted by existing LDP-based approaches, leading to severe degradation of data utility. In this paper, we focus on real-time data collection under a honest-but-curious server, and propose a novel pattern-aware privacy-preserving approach, called PatternLDP, to protect data privacy while the pattern of time-series can still be preserved. To this end, instead of providing the same level of privacy protection at each data point, each user only samples remarkable points in time-series and adaptively perturbs them according to their impacts on local patterns. In particular, we propose a pattern-aware sampling method based on Piecewise Linear Approximation (PLA) to determine whether to sample and perturb current data point. To reduce the utility loss caused by pattern change after perturbation, we propose an importance-aware randomization mechanism to adaptively perturb sampled data locally while achieving better trade-off between privacy and utility. A novel metric-based w-event privacy is introduced to measure the privacy protection degree for pattern-rich time-series. We prove that PatternLDP can provide the above privacy guarantee, and extensive experiments on real-world datasets demonstrate that PatternLDP outperforms existing mechanisms and can effectively preserve the important patterns.