Abstract
Stream data from real-time distributed systems such as IoT, tele-health, and crowdsourcing has become an important data source. However, the collection and analysis of user-generated stream data raise privacy concerns due to the potential exposure of sensitive information. To address these concerns, local differential privacy (LDP) has emerged as a promising standard. Nevertheless, applying LDP to stream data presents significant challenges, as stream data often involves a large or even infinite number of values. Allocating a given privacy budget across these data points would introduce overwhelming LDP noise to the original stream data. Beyond existing approaches that merely use perturbed values for estimating statistics, our design leverages them for both perturbation and estimation. This dual utilization arises from a key observation: each user knows their own ground truth and perturbed values, enabling a precise computation of the deviation error caused by perturbation. By incorporating this deviation into the perturbation process of subsequent values, the previous noise can be calibrated. Following this insight, we introduce the Iterative Perturbation Parameterization (IPP) method, which utilizes current perturbed results to calibrate the subsequent perturbation process. To enhance the robustness of calibration and reduce sensitivity, two algorithms, namely Accumulated Perturbation Parameterization (APP) and Clipped Accumulated Perturbation Parameterization (CAPP) are further developed. We prove that these three algorithms satisfy $w$-event differential privacy while significantly improving utility. Experimental results demonstrate that our techniques outperform state-of-the-art LDP stream publishing solutions in terms of utility, while retaining the same privacy guarantee.
Introduction
In the era of real-time distributed systems, stream data—continuous sequences of values such as GPS coordinates, sensor readings, or electricity usage—has become a cornerstone of modern analytics. However, the collection of this data by central servers poses significant privacy risks. Local Differential Privacy (LDP) has emerged as the gold standard for addressing these risks, as it allows users to perturb their data locally before transmission, ensuring that no trusted third party is required.
Despite its strengths, LDP faces a fundamental hurdle when applied to stream data: the "privacy budget" ($\epsilon$). In a continuous stream, the budget must be distributed across an infinite or very large number of data points. If the budget is split too thinly, the resulting noise becomes so high that it drowns out the actual signal. Existing solutions often attempt to mitigate this by sampling data at specific "turning points" or weakening privacy guarantees, but these methods frequently result in a loss of temporal detail or accuracy. This paper, accepted for the IEEE International Conference on Data Engineering (ICDE 2025), introduces a novel "dual utilization" approach to overcome these limitations.
The Core Innovation: Dual Utilization
The researchers identified a critical oversight in traditional LDP implementations: while the server only sees the noisy data, the user's device knows both the "ground truth" ($x$) and the "perturbed version" ($x'$) sent to the server. Consequently, the user can calculate the exact deviation error ($d = x - x'$) introduced by the privacy mechanism.
Instead of treating this noise as an unavoidable loss, the proposed framework uses it as a calibration tool. By incorporating the error from a previous time step into the perturbation process of the next data point, the system can effectively "cancel out" accumulated noise over time. This transforms the perturbed values from mere outputs into internal parameters that guide the privacy mechanism itself.
Methodology: Perturbation Parameterization (PP)
The authors developed a family of algorithms based on this feedback loop concept, termed Perturbation Parameterization (PP):
- IPP (Iterative Perturbation Parameterization): This baseline method takes the error from the immediate previous time step and adds it to the current value before perturbation. If the previous value was pushed "too high" by noise, the next value is adjusted "lower" to compensate, keeping the expected sum of the stream close to the true sum.
- APP (Accumulated Perturbation Parameterization): To prevent errors from drifting over longer sequences, APP tracks the total accumulated deviation across the stream, providing a more stable calibration.
- CAPP (Clipped Accumulated Perturbation Parameterization): To ensure that large adjustments do not push data into extreme ranges—which would require even more noise to protect—CAPP introduces a "clipping" step. This optimizes the trade-off between discarding error and managing sensitivity, making it the most robust algorithm in the suite.
- PP-S (Sampling): For environments with extremely tight privacy budgets, the authors developed a sampling-based version that mathematically determines the optimal frequency of data transmission to maximize Mean Squared Error (MSE) performance.
Experimental Evaluation
The effectiveness of these algorithms was tested against state-of-the-art techniques (such as ToPL and BA-SW) across four real-world datasets and one synthetic dataset:
- Volume: Highway traffic measurements from Minnesota.
- C6H6: Benzene concentrations from air quality sensors.
- Taxi: GPS trajectories from 10,000 taxis in Beijing.
- Power: Electricity usage from 25,000 devices.
- Sin-data: High-dimensional synthetic sinusoidal data.
Key Findings
- Superior Utility: The CAPP algorithm demonstrated massive utility gains, with some tests showing the error (MSE) of previous methods was over 100 times higher than the proposed approach.
- Privacy Guarantee: All proposed algorithms were proven to satisfy $w$-event differential privacy, ensuring rigorous protection over sliding windows of time.
- Scalability: The methods proved effective not just for individual-level estimation, but also for maintaining high accuracy in population-level statistics, such as city-wide traffic distributions.
Conclusion and Future Work
By reframing privacy noise as a parameter for future calibration, this research provides a path forward for high-accuracy stream data collection under LDP. While currently optimized for numerical data, the "dual utilization" logic opens new doors for privacy-preserving analytics in IoT and edge computing.
Future research will focus on extending these techniques to categorical data (such as discrete events or strings) and developing more adaptive, data-driven heuristics for the clipping bounds used in the CAPP algorithm. As decentralized networks continue to grow, these methods will be vital for balancing the need for real-time insights with the fundamental right to data privacy.
Summary updated