Dual Utilization of Perturbation for Stream Data Publication under Local Differential Privacy

Rong Du, Qingqing Ye ∗ , Yaxin Xiao, Liantong Yu, Yue Fu, Haibo Hu · 2025

Read Dual Utilization of Perturbation for Stream Data Publication under Local Differential Privacy by Rong Du, Qingqing Ye ∗ , Yaxin Xiao, Liantong Yu, Yue Fu, Haibo Hu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14993.txt.

Introduction

Rong Du and five co-authors worked on keeping stream data private while it is shared. Their paper, from twenty twenty-five, deals with data that flows in from devices, health tools, and crowd sources. Such streams can hold vast or endless values. A local privacy method adds noise to each value to hide the source. But the noise can swamp the stream when values are many.

Past designs used the noisy values just to guess broad stats. This design uses them twice, both to mask and to guess. That dual use aims to keep the guess sharp on a fixed privacy budget. Readers who share live data get a way to guard users with less loss of worth.

Catalog record

CREATORRong Du, Qingqing Ye ∗ , Yaxin Xiao, Liantong Yu, Yue Fu, Haibo Hu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-14993

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dual Utilization of Perturbation for Stream Data Publication under Local Differential Privacy Thanks: ∗ Corresponding author: Qingqing Ye Rong Du, Qingqing Ye ∗ , Yaxin Xiao, Liantong Yu, Yue Fu, Haibo Hu 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 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. I Introduction In the era of big data, collecting and analyzing real-time data streams are essential in many distributed systems such as IoT, tele-health, and crowdsourcing, which continuously generate ample amount of data. Typical examples include real-time traffic updates for navigation systems such as Google Maps and Waze [ 12 ] , and consumer sentiment analysis on peer review platforms like Yelp [ 34 ] . While these stream data offer substantial benefits for big data analysis and training AI models, they simultaneously bring forth privacy issues due to the potential exposure of sensitive personal information [ 13 , 5 ] . Local Differential Privacy (LDP) [ 3 , 6 , 16 ] , a cryptographic technique extensively deployed in various real-world contexts [ 11 , 29 , 4 , nguyen2016collecting ] , provides formal privacy guarantees by bounding the information leakage of individual users through a privacy parameter \epsilon . However, its direct application to stream data faces fundamental limitations. In particular, user-level LDP [ 1 ] considers the worst-case scenario and partitions the privacy budget according to the composition theorem [ 19 ] , where privacy budget division across timestamps leads to exponential utility degradation as accumulated noise overwhelms the original data. To address the challenge of limited privacy budget in stream data collection, two mainstream approaches have emerged in existing research, i.e., relaxing privacy definitions and reducing the amount of transmitted data. For privacy relaxation, event-level LDP [ 1 , 31 ] assigns independent privacy budgets \epsilon to individual data points, which improves utility at the cost of weakened privacy guarantees across multiple timestamps. w -event LDP [ 17 ] provides a more rigorous privacy guarantee by constraining the budget allocation within sliding windows of length w . For reducing data transmission, methods proposed in [ 11 , 32 ] allow users to report only at turning points, allocating more privacy budget to each reported point. However, reporting at turning points reveals temporal information, as the transmission time itself indicates when the original data changes. To decouple the relationship between turning points and time, Mao et al. [ 21 ] proposed PrivShape, which first employs symbolic aggregate approximation to convert numerical sequences into short strings, and then uses tree structures to identify frequent string patterns. However, due to the loss of detailed information, this method does not perform well in estimating means and distributions for range queries. Therefore, enhancing the utility while preserving user privacy remains a key challenge in LDP-enabled stream data analysis. Departing from privacy budget allocation strategies, we propose a novel approach that leverages perturbation results of steam data in a dual manner. Beyond their conventional role in statistical analysis, these results can serve as valuable components for calibrating perturbation parameters. This dual-purpose approach stems from a key observation that each user knows both their own ground truth and perturbed values, which enables the deviation error to be computed precisely and in turn incorporated into subsequent values to calibrate the previous noise. Leveraging this auxiliary information, users can employ their locally perturbed values to adjust subsequent inputs for the perturbation mechanism \mathcal{A} , effectively mitigating errors from previous perturbations. We rigorously prove that this approach satisfies w -event LDP, as the adjust inputs process naturally dilutes individual value information. To implement this idea, we first introduce the Iterative Perturbation Parameterization (IPP) algorithm as a strawman proposal, which incorporates the deviation from the previous perturbation to the current stream value as input for \mathcal{A} . Since the current perturbation is a cumulative effect of all previous data points rather than just the nearest one, we present the Accumulated Perturbation Parameterization (APP) algorithm to determine the deviations up to the current stream value. Through this process, the sensitivity increases as the range of the aggregated result expands. To mitigate this, we propose the Clipped Accumulated Perturbation Parameterization (CAPP), an optimized version of the APP that can reduce sensitivity while retaining most of the perturbation information. Additionally, we extend our perturbation parameterization scheme to time-slot sampling, which is particularly advantageous for mean statistics of subsequences while ensuring the accuracy of the published stream data. Our contributions are summarized as follows: • To the best of our knowledge, this is the first work that parameterizes input value based on perturbation for publishing stream data under LDP, which significantly enhances utility over existing state-of-the-art techniques. • We define a new problem of subsequence data collection under LDP, for statistical analysis on subsequences influenced by LDP while retaining rigorous privacy guarantee, i.e., w -event LDP. • We propose a time-slot sampling approach for subsequence mean statistics estimation over user sampling, which further improves the utility of subsequence mean estimation. The remainder of this paper is organized as follows. In Section II , we introduce some preliminaries of LDP. In Section III , we formally define the problem and present a baseline approach to demonstrate our core ideas. In Section IV , we propose two optimized algorithms, followed by a sampling-based solution in Section V . In Section VI , we provide extensive experimental evaluations. Then we review related studies in Section VII , and conclude the paper in Section VIII . II Preliminaries II-A Local Differential Privacy Local Differential Privacy (LDP) [ 6 , 16 ] is a modern privacy-preserving standard that enables users to anonymize their data before publishing. It is defined as follows: Definition 1 . A randomized algorithm \mathcal{A} satisfies \epsilon -local differential privacy ( \epsilon -LDP), if and only if for any two values x and x^{\prime} , and

Read the complete text