arXiv CSopen access

Personalized w-Event Privacy for Infinite Stream Estimation

Noname manuscript No. (will be inserted by the editor)

Personalized w-Event Privacy for Infinite Stream Estimation

arXiv:2605.09054v1 [cs.DB] 9 May 2026

Leilei Du1 · Xu Zhou1 · Peng Cheng2 · Lei Chen3,4 · Xuemin Lin5 · Wei Xi6 · Kenli Li1

Received: date / Accepted: date

Abstract In many real-life applications, such as event monitoring, log analysis and video querying, w-event privacy is widely used to protect individual privacy within a given time window while maintaining high accuracy in data collection. However, existing w-event privacy studies on infinite data stream typically focus only on homogeneous privacy requirements for all users. In this paper, we propose personalized w-event privacy protection that enables users to set different privacy requirements in private data stream estimation. Specifically, we first design a Personalized Window Size Mechanism (PWSM) that allows users to maintain personalized privacy requirements at each time slot. Then,

Peng Cheng [email protected]

we propose two solutions—Personalized Budget Distribution (PBD) and Personalized Budget Absorption (PBA)—to accurately estimate streaming data statistics while achieving w-Event E Personalized Differential Privacy ((w, E)EPDP). PBD ensures that the privacy budget for the next time step is at least equal to the amount consumed in the previous release. PBA enhances the current time slot’s privacy budget by combining the privacy budget from the previous k time slots and borrowing from the next k time slots. In addition, we design two additional solutions—Dynamic Personalized Budget Distribution (DPBD) and Dynamic Personalized Budget Absorption (DPBA)—that allow users to dynamically adjust their privacy requirements at each time slot while achieving (τ , wB , wF )-Event (E B , E F )-Personalized Differential Privacy ((τ , wB , wF , E B , E F )-EPDP). The proposed methods are all proven to achieve personalized differential privacy levels and establish error upper bounds for each method. From the experimental results, our methods outperform the state-of-the-art algorithms with at least 53.6% smaller error.

Lei Chen [email protected]

Keywords Differential privacy · Stream data · Event privacy · Personalized privacy

Leilei Du [email protected] Xu Zhou [email protected]

Xuemin Lin [email protected] Wei Xi [email protected] Kenli Li [email protected] 1

Hunan University, Changsha, China Tongji University, Shanghai, China 3 HKUST (GZ), Guangzhou, China 4 HKUST, HK SAR, China 5 Shanghai Jiaotong University, Shanghai, China 6 Xi’an Jiaotong University, Xi’an, China 2

1 Introduction With the widespread adoption of smart devices and wireless networks, more people are sharing and receiving data through various platforms, making real-time analysis (e.g., event monitoring [23], log analysis [42], and video querying [32]) increasingly necessary. During these data collection and analysis processes, protecting users’ privacy is crucial. To prevent user data leakage, Differential Privacy (DP) has emerged as a widely adopted solution in data publishing and statistical analysis.

Leilei Du1 et al.

2

Fig. 1: Different event window sizes for different time slots.

Existing w-event privacy mechanisms [37, 41, 34] based on DP protect user data privacy across consecutive events. However, these mechanisms use uniform privacy requirements for all users (applying the same privacy budget E and window size w). This one-size-fits-all approach has significant limitations in real-world applications. For example, celebrities in the entertainment industry may require strong protection of their location data, while street artists may want to share their locations to gain visibility. The fixed privacy budget and window size thus provide inadequate privacy protection for some users while unnecessarily increasing data error rates (excessive privacy protection) for others. Example 1 Consider an example of online car-hailing shown in Figure 1. It has 100 drivers U = {u1 , ..., u100 } who share their locations from {loc1 , ..., loc5 } at each time slot. Each driver ui is protected by wi -event privacy, meaning their location data is safeguarded through E-DP across at least wi consecutive time slots, where E represents their required privacy protect strength. For example, u1 requires location protection across any 4 consecutive time slots, while u99 and u100 need protection across any 8 consecutive time slots. For the drivers ui ∈ U \{u99 , u100 }, the window sizes do not exceed 4. By traditional w-event privacy with E = 1, it necessitates setting the event window sizes to the maximal value (i.e., w = 8) for satisfying all drivers’ privacy requirements. While this achieves 8-event privacy—providing the strongest privacy protection—it also results in the lowest data utility. Let AEavg denote the average square error at each time slot. When using the Laplace mechanism, the error at any the variance of added  time slot equals  2  1 Laplace noise i.e., AEavg = 2 × ϵ/w . Using the Uniform method [25], the error is AEavg = 2 × ( wϵ )2 = 128 under 8event privacy. While the first 98 drivers only require 4-event privacy. Setting the privacy level to 4-event privacy would
2 reduce the error to AEavg = 2 × wϵ = 32. However, 4event privacy only protects data within a window size of 4, which cannot meet the privacy requirements of the 99-th and the 100-th drivers who need protection within a window size of 8, thus compromising their privacy.

Challenges. From the example above, there are three main challenges: (1) Unified Privacy Budget. Traditional DP requires a uniform privacy budget ϵ for all users to achieve ϵ-DP. However, users have distinct privacy budgets (a type of privacy requirements). While setting ϵ to the minimum value would satisfy everyone’ privacy requirements, this approach significantly reduces data utility. The challenge lies in unifying users’ distinct privacy budgets into a single value while maximizing the utility of published data. (2) Personalized Privacy Budget Allocation. The rate of change in streaming data fluctuates over time. Within a given window size, time slots with rapid changes contain more information compared to those with slower changes. Since the privacy budget serves as a privacy protection resource, it should be allocated primarily to time slots containing more information. The challenge is determing how to optimally distribute each user’s personalized privacy budget across their privacy window size. (3) Dynamic Privacy Requirements. Users have different privacy requirements at different time slots. These varing requirements can lead to privacy budget waste or privacy requirement conflicts between current and historical time slot. The challenge is how to allocate varying privacy budgets while maintaining high utility. A further challenge is that the dynamic personalized setting is not a straightforward extension of the fixed one. In the fixed case, each user keeps the same privacy requirement over time. In contrast, in the dynamic case, privacy requirements may vary across timestamps, so each release must remain consistent with previously consumed privacy budgets while preserving feasibility for future requirements. Moreover, although privacy constraints are specified at the user level, the system still publishes one shared aggregate result at each timestamp. Therefore, the dynamic personalized setting introduces a new online feasibility problem under heterogeneous time-varying constraints. Contributions. This paper studies a more general problem than the fixed personalized setting, namely Dynamic Personalized w-Event Private Publishing for Infinite Data Streams (DPWEPP-IDS), where each user may specify time-varying backward and forward privacy requirements. This setting is practically important because privacy preferences in real systems may evolve over time, and technically challenging because each release must remain compatible with both historical budget consumption and future privacy feasibility. To address this problem, we develop a unified view of personalized stream release. Our main observation is that heterogeneous personalized privacy requirements must ultimately be transformed into a valid system-level release decision, because only one aggregate statistic is published at each time slot. The main contribution is not replacing a global window or budget with personalized parameters, but

Personalized w-Event Privacy for Infinite Stream Estimation

3 Table 1: Summary for related work.

constructing and maintaining a valid shared release budget under overlapping, heterogeneous, and time-varying personalized privacy requirements. This heterogeneous-to-release unification challenge does not arise in classical homogeneous w-event privacy. We summarize our contributions as follows: – We formulate Dynamic Personalized w-Event Private Publishing for Infinite Data Streams and define the corresponding privacy notation, namely (τ , wB , wF )-Event (E B , E F )-Personalized Differential Privacy ((τ , wB , wF , E B , E F )-EPDP), which generalize the fixed personalized setting in Section 3. – We identify a new online feasibility challenge under dynamic personalized privacy: at each timestamp, the mechanism must reconcile heterogeneous user-specific requirements with both past budget consumption and future privacy feasibility, while still producing one shared aggregate release in Section 3. – We propose a unified framework for personalized stream release. In the fixed setting, this framework is instantiated as PWSM with two mechanisms, PBD and PBA in Section 4. In the dynamic setting, it is generalized to DPWSM with two mechanisms, DPBD and DPBA in Section 5. – We provide privacy guarantees and utility bounds for all mechanisms, analyze their computational properties in Section 4 and 5, and experimentally evaluate them on real and synthetic datasets in Section 6. Compared with the conference version [13], this paper studies a more general setting in which each user’s privacy requirement may vary over time. This generalization introduces a new online feasibility problem: each release must satisfy heterogeneous user-specific privacy constraints while remaining consistent with previously consumed budgets and feasible for future requirements. To address this problem, we develop the dynamic framework DPWSM together with two mechanisms, DPBD and DPBA, and provide corresponding privacy guarantees, utility analysis, and new experiments for this generalized setting. 2 Related Work We classify the related work in the area of data stream estimation under differential privacy and non-uniformity differential privacy. 2.1 Data Stream Estimation under Differential Privacy Based on the privacy model, there are three types of data stream estimation methods: centralized differential privacy [16] (CDP) based methods, local differential privacy [4] (LDP) based methods and shuffled differential privacy [9, 10]. Data Stream Estimation under CDP. Dwork et al. [18] first address the problem of Differential Privacy (DP) on data

Infinite & correlated % %

Personalized privacy % %

%

%

% % "

% % %

"

%

" " " " " " % % " " "

% % % % % % % % % % %

LDP-IDS [34]

"

%

Concurrent-SDP [36]

"

%

LPS-SS [28] ExSub [38] HDP [1] PDP [24] OSDP [26] Geo-I [2] Record heterogenous PWSM, VPDM [40] PUCE, PGT [14] PFA, PFA+ [31] Our mechanisms

% % % % % % % % % "

% % % " " " " " " "

Model Types

event-level privacy

Centralized DP

user-level privacy

w-event privacy event-level privacy Local DP

user-level privacy w-event privacy event-level privacy

Shuffled DP

user-level privacy Item heterogeneous

Methods Finite B-tree [18] Infinite B-tree [7] Adaptive-density Counter [17] Decayed Privacy [6] PeGaSus [8] FAST [21] Private heterogeneous mean estimation [11] Dynamic user-DP [12] DPI [22] SMM-TM, RBM [15] BD, BA [25] ResuseDP [37] SPAS [29] RAPPOR [20] ToPL [39] CGM [3] DDRM [43] StaSwitch [46]

streams. They define two types of DP levels: event-level differential privacy (event-DP) and user-level differential privacy (user-DP). In event-DP, each single event is hidden in statistic queries. Dwork et al. [18] focus on the finite event scenarios and propose a binary tree method to achieve high statistical utility while maintaining event-DP. Chan et al. [7] extend it to infinite cases, and produce partial summations for binary counting. Dwork et al. [17] introduce a cascade buffer counter that updates adaptively based on stream density. Bolot et al. [6] propose decayed privacy which reduces the privacy costs for past data. Chen et al. [8] develop PeGaSus, a perturb-group-smooth framework for multiple queries under event-DP. However, event-DP assumes all element in a stream are independent, making it unsuitable for correlated data stream publishing. In user-DP, all events for each user are hidden in statistic queries. Fan et al. [21] propose the FAST algorithm, which uses a sampling-and-filtering framework to count finite stream data under user-DP. Cummings et al. [11] address heterogeneous user data by estimating populationlevel means while achieving user-DP. However, they only consider finite data. Dong et al. [12] introduce continual observation mechanisms under user-DP for dynamic data streams, achieving utility guarantees without prior data restrictions and providing down-neighborhood optimality for count and sum functions. However, their approach assumes

4

independence between different stages. Feng et al. [22] develop the DPI framework with bidrectional reweighting, 0DP synopsis generation, and dynamic error control, ensuring that privacy preservation does not significantly degrade accuracy over time. Dvijotham et al. [15] tackle cascading correlations in data through two methods: Streaming Matrix Multiplication for Toeplitz Matrices (SMM-TM) and Recursive Binary Tree Mechanism (RBM). These approaches reduce the impact of data dependencies on differential privacy in streaming continual counting tasks. However, providing user-DP for infinite data requires infinite perturbation, resulting in poor long-term utility [25]. To bridge the gap between event-DP and user-DP, Kellaris et al. [25] propose w-event DP for infinite streams. This ensures ϵ-DP for any group of events within a time window of size w. They introduce two methods, Budget Distribution (BD) and Budget Absorption (BA), to optimize privacy budget use and estimate statistics effectively. However, neither method handles stream data with significant changes. Wang et al. [37] apply the w-event concept to the FAST method, proposing a multi-dimensional stream release mechanism called ResueDP, which achieves accurate estimation for both rapid and slow data stream changes. Li et al. [29] propose SPAS for the continuous release of infinite data streams under w-event differential privacy. It improves adaptability through data-dependent strategy prediction, adaptive sampling, and privacy budget allocation. However, SPAS assumes a single global privacy requirement and does not support heterogeneous user-specific privacy budgets or window sizes, nor dynamically changing personalized requirements over time. Overall, existing centralized methods for w-event private stream release, including BD, BA, ResueDP, and SPAS, are designed for the classical homogeneous setting with a single global privacy requirement, and do not model heterogeneous user-specific privacy requirements or their time-varying extensions. Data Stream Estimation under LDP. To overcome the dependence on a trusted server, LDP [4] has recently been proposed and adopted by many major companies such as Microsoft, Apple and Google. Similary to DP, data stream estimation under LDP can be classified into event-LDP, userLDP and w-event LDP. Erlingsson et al. [20] introduce RAPPOR to estimate finite streams under LDP. They design a two-layer randomized response mechanism (i.e., permanent randomized response and instantaneous randomized response) to protect each individual’s data. Wang et al. [39] extend event-level privacy from CDP to LDP and design the efficient ToPL method under event LDP. Nevertheless, both RAPPOR and ToPL focuses solely on event-level privacy, lacking privacy protection for correlated data in streams. To address the problem of correlated time series data, Bao et al. [3] propose CGM, an (ϵ, δ)-LDP method that uses

Leilei Du1 et al.

the analytic Guassian mechanism for streaming data collection. However, CGM is limited to finite streaming data. Xue et al. [43] introduce DDRM for continual frequency estimation under LDP. While it dynamically allocates privacy budgets and employs difference trees to reduce unnecessary consumption, DDRM suffers from eventual budget depletion, which compromises estimation accuracy. Ye et al. [46] develop the StaSwitch mechanism, which employs a stateful switch operation for efficient privacy budgetmanagement. Though this allows flexible privacy parameter settings and improves data utility, the budget still accumulates over time. Ren et al. [34] introduce LDP-IDS for infinite streaming data collection and analysis under w-event LDP. They propose two budget allocation methods and two population allocation methods, bridging the gap between event LDP and user LDP while improving estimation accuracy. However, all these methods cannot be adopted to support personalized event window sizes. Data Stream Estimation under SDP. Tenenbaum et al. [36] propose a shuffle-based continual observation mechanism that supports concurrent streaming queries with provable accuracy guarantees. However, its privacy notion is limited to event-level and does not extend to user-level protection. Li et al. [28] propose a shuffle-based LDP streaming framework with subsampling that achieves double privacy amplification and improved utility. However, it is only suitable for finite stream data. Wang et al. [38] propose ExSub, a user-level differentially private streaming analytics framework under the local and shuffle models that achieves nearcentralized accuracy for finite-length data streams. However, it relies on bounded user changes and a predefined time horizon. 2.2 Personalized and Heterogeneous Differential Privacy Recently, some studies address the non-uniform privacy requirements among items (table columns) or records (table rows) [33]. Alaggan et al. [1] first examine scenarios where each database instance comprises a single user’s profile. They focus on varying privacy requirements for different items and formally define Heterogeneous Differential Privacy (HDP). Jorgensen et al. [24] investigate the privacy preservation for individual rows, introducing Personalized Differential Privacy (PDP). They design two mechanisms leveraging non-uniform privacy requirements to achieve better utility than standard uniform DP. Kotsogiannis et al. [26] recognize that different data have different sensitivity, then define One-sided Differential Privacy (OSDP) and propose algorithms that truthfully release non-sensitive record samples to enhance accuracy in DP-solutions. Andrés et al. [2] introduce a novel non-uniform privacy concept called GeoIndistinguishability (Geo-I), where the privacy level for any point increases as the distance to this point decreases. Wang et al. [40] and Du et al. [14] explore PDP in spatial crowd-

Personalized w-Event Privacy for Infinite Stream Estimation

sourcing, and develop highly effective private task assignment methods to satisfy diverse workers’ privacy and utility requirements. Liu et al. [31] investigate HDP in federated learning. They assume different clients hold DP budget and divide them into private and public parts, then propose two methods to project the “public” clients’ models into “private” clients’ models to improve the joint model’s utility. More recently, Sun et al. [35] propose Personalized Truncation for personalized differential privacy (PDP) in count, sum, and SJA query processing. This line of work is related in spirit but does not consider infinite-stream continual release or w-event privacy. However, all above studies are not suitable for stream data. 3 Problem Settings In this section, we introduce key concepts, including data streams and differential privacy (DP). We then define two types of personalized privacy requirements that address different real-world scenarios. Finally, we provide the problem definition of Dynamic Personalized w-Event Private Publishing for Infinite Data Streams (DPWEPP-IDS). Table 2 summarizes the notations used throughout this paper. Table 2: Notations. Notations D Dt S U ui xi,t ct rt ϵ ϵi w wi E Ei wB,t wB,i,t E B,t EB,i,t wF,t wF,i,t E F,t EF,i,t

Description the database domain a database at time slot t a data stream the user set the i-th user in U ui ’s data at time slot t a real statistical histogram at time slot t an estimation statistic histogram at time slot t all users’ privacy budget requirement at any time slot ui ’s privacy budget requirement in at any time slot all users’ fixed window size requirements ui ’s fixed window size requirement all users’ fixed privacy budget requirements ui ’s fixed privacy budget requirement all users’ backward window size requirements at time slot t ui ’s backward window size requirement at time slot t all users’ backward privacy budget requirement at time slot t ui ’s backward privacy budget requirement at time slot t all users’ forward window size requirement at time slot t ui ’s forward window size requirement at time slot t all users’ forward privacy budget requirement at time slot t ui ’s forward privacy budget requirement at time slot t

3.1 Data Stream Definition 1 (Data Stream [25]). Let Dt ∈ D be a database with d columns and n rows (each row representing a user) at t-th time slot. The infinite database sequence S = [D1 , D2 , . . .] is called a data stream, where S[t] is the t-th element in S (i.e., S[t] = Dt ). For any data stream S, a substream between time slot tl and tr (where tl < tr ) is denoted as Stl ,tr =

5

[Dtl , Dtl +1 , . . . , Dtr ]. When tl = 1, we denote St = [D1 , D2 , . . . , Dt ] as the stream prefix of S. Definition 2 (Data Stream Count Publishing). Let Q : D → Rd be a count query. Then, Q(S[t]) = Q(Dt ) = ct is the count data to be published at time slot t, where ct (j) represents the count of the j-th column of Dt . The infinite count data series [c1 , c2 , . . .] is called a data stream count publishing. Definition 3 (w-neighboring stream prefixes [7, 25]). Let w be a positive integer, two stream prefixes St , St′ are wneighboring (i.e., St ∼w St′ ), if 1. for each St [k], St′ [k] such that k ≤ t and St [k] ̸= St′ [k], it holds that St [k] and St′ [k] are neighboring [25] in centralized DP, and 2. for each St [k1 ], St [k2 ], St′ [k1 ], St′ [k2 ] with k1 < k2 , St [k1 ] ̸= St′ [k1 ] and St [k2 ] ̸= St′ [k2 ], it holds that k2 − k1 + 1 ≤ w. Definition 4 ((τ, w)-backward neighboring stream prefixes). Let w be a positive integer. Two stream prefixes St , St′ are (τ, w)-backward neighboring (denoted as St ∼B,τ,w St′ ), if 1. for each St [k], St′ [k] such that k ∈ [t] and St [k] ̸= St′ [k], it holds that St [k] and St′ [k] are neighboring, and 2. for each St [k], St′ [k], with k < τ , St [k] ̸= St′ [k], it holds that τ − k + 1 ≤ w. Definition 5 ((τ, w)-forward neighboring stream prefixes). Let w be a positive integer. Two stream prefixes St , St′ are w-forward neighboring (denoted as St ∼F,τ,w St′ ), if 1. for each St [k], St′ [k] such that k ∈ [t] and St [k] ̸= St′ [k], it holds that St [k] and St′ [k] are neighboring, and 2. for each St [k], St′ [k], with k > τ , St [k] ̸= St′ [k], it holds that k − τ + 1 ≤ w.

Remark 1 (Equivalence of forward and shifted backward neighboring). For any τ and w, the (τ, w)-forward neighboring relation is equivalent to the (τ + w − 1, w)-backward neighboring relation, since both restrict the changed events to the same window [τ, τ +w−1]. We nevertheless keep both notations because they correspond to two semantically different types of dynamic privacy requirements in our model: a backward requirement is anchored at the current time slot and constrains privacy loss accumulated from the recent past, whereas a forward requirement is declared at the current time slot and constrains feasible future releases in the upcoming window. This distinction is convenient for stating user requirements and for presenting the online feasibility rules in Section 5.

Leilei Du1 et al.

6

3.2 Differential Privacy There are two parts in the differential privacy paradigm: a large number of respondents (data owners) and a trust curator (server). The goal of differential privacy mechanisms is to publish statistic of D while not comprise the privacy of respondents. Threat Model. This work follows the centralized-DP paradigm. A trusted curator collects the stream data xi,t and the corresponding personalized privacy requirements from users, and releases only perturbed aggregate statistics rt . The adversary is any party that observes the released sequence (r1 , r2 , . . . ). As is standard in differential privacy, we assume the adversary knows the mechanism, the neighboring relation, and all public system parameters, and may have arbitrary side information. Our privacy objective is therefore to bound the information leaked about any user’s contribution within the relevant event window through the released outputs. This trusted-curator assumption is consistent with prior centralized w-event stream release methods reviewed in Section 2. Definition 6 (ϵ-differential privacy [16, 25]). A mechanism M : D → O satisfies ϵ-differential privacy (or ϵ-DP), where ϵ ≥ 0 if for all sets O ⊆ O, and every pair of neighboring databases D, D′ ∈ D, it holds that

possible outputs of M. Let U be the set of all users. Then M is (τ , wB , wF )-Event (E B , E F )-Personalized Differential Privacy (or (τ , wB , wF , E B , E F )-EPDP) if ∀O ⊆ O, ∀i ∈ [|U |] with (wB,i , wF,i , EB,i , EF,i ) ∈ (wB , wF , E B , E F ) and ∀St , St′ satisfying St ∼B,τ,wB,i St′ and St ∼F,τ,wF,i St′ , it holds that Pr[M (St ) ∈ O] ≤ eEB,i +EF,i Pr[M (St′ ) ∈ O].

Scope and Limitation of Protection. The proposed notions (w, E)-EPDP and (τ , wB , wF , E B , E F )-EPDP protect user data contributions, rather than the privacy preferences themselves. In particular, the personalized budgets and window sizes are treated as mechanism parameters. These notions inherit the bounded-window semantics of classical w-event privacy: they protect each user’s contribution only within the corresponding fixed or dynamic event window through the released outputs, but do not provide full trajectory-level privacy over an unbounded stream. Therefore, our goal is not to resolve the general trajectory-level limitation of w-event privacy, but to extend the w-event paradigm to heterogeneous and time-varying personalized privacy requirements. The trusted curator assumption is standard in centralized stream release; protecting against an untrusted curator is outside the scope of this paper and belongs to local/shuffled privacy settings.

Pr[M(D) ∈ O] ≤ eϵ · Pr[M(D′ ) ∈ O].

Definition 7 (ϵ-Personalized Differential Privacy [24]). Given a set of users U = {u1 , . . . , un } with privacy requirements (preferences) ϵ = {ϵ1 , . . . , ϵn }, a randomized mechanism M : D → O satisfies ϵ-personalized differential privacy (or ϵ-PDP), if for every pair of neighboring tpi datasets D, D′ ⊆ D with D, D ∼ D′ [24], and for all sets O ⊆ O of possible outputs, it holds that Pr[M(D) ∈ O] ≤ eϵi · Pr[M(D′ ) ∈ O],

(1)

where tpi is the tuple set associate with ui . Definition 8 (w-Event E Personalized Differential Privacy). Let M be a mechanism that takes a stream prefix of arbitrary size as input. Let O be the set of all possible outputs of M. Let U be the set of all users. M is w-Event E Personalized Differential Privacy (or (w, E)-EPDP) if ∀O ⊆ O, ∀i ∈ [|U |] with wi ∈ w and Ei ∈ E and ∀St , St′ satisfying St ∼wi St′ , it holds that Pr[M (St ) ∈ O] ≤ eEi Pr[M (St′ ) ∈ O].

(2)

When w = 1, (w, E)-EPDP simplifies to E-PDP [24]. Definition 9 ((τ , wB , wF )-Event (E B , E F )-Personalized Differential Privacy). Let M be a mechanism that takes a stream prefix of arbitrary size as input. Let O be the set of all

3.3 Personalized Privacy Requirement In this paper, we consider two kinds of personalized privacy requirements. Fixed Personalized Privacy Requirement. For any user ui , they have a privacy level requirement Ei within a specific window size wi meaning the privacy level in this window should achieve Ei -DP. We define wi as the fixed personalized window size requirement and Ei as the fixed personalized privacy budget requirement. Together, the pair (wi , Ei ) constitutes the fixed personalized privacy requirement. Dynamic Personalized Privacy Requirement. For any user ui at time slot t, there are two privacy requirements: a dynamic backward requirement and a dynamic forward requirement. The backward requirement specifies a privacy level EB,i,t within a dynamic backward window size wB,i,t , with the window ending at time slot t to achieve EB,i,t DP. The forward requirement specifies a privacy level EF,i,t within a dynamic forward window size wF,i,t , with the window beginning at time slot t to achieve EF,i,t -DP. These components constitute ui ’s backward window size requirement at time slot t, backward privacy budget requirement at time slot t, forward window size requirement at time slot t, and forward privacy budget requirement at time slot t. Together, the pairs (wB,i,t , EB,i,t ) and (wF,i,t , EF,i,t ) form ui ’s

Personalized w-Event Privacy for Infinite Stream Estimation

backward privacy requirement at time slot t and forward privacy requirement at time slot t, respectively. Although the forward requirement can be equivalently rewritten as a shifted backward requirement, we keep the forward form because it directly captures the user’s requirement declared at time slot t for the future window starting from t. 3.4 DPWEPP-IDS Given a data stream S, the analyst aims to obtain the data stream count (i.e., original count) publishing as c = [c1 , c2 , . . .]. To protect user privacy, however, the analyst only receives the obfuscated data stream count (i.e., estimation count) r = [r 1 , r 2 , . . .]. The goal of the problem is to minimize the difference between the estimation count and the original count while meeting the personalized privacy requirement. We present our problem definition as follows. Definition 10 (Dynamic Personalized w-Event Private Publishing for Infinite Data Streams). Given a user set U = {u1 , u2 , . . . , un } where each ui holds a data collection (wB,i,t , EB,i,t , wF,i,t , EF,i,t , xi,t ) at time slot t. All xi,t for ui ∈ U at time slot t form Dt . All Dt consist an infinite data stream D = [D1 , D2 , . . .]. Dynamic Personalized w-Event Private Publishing for Infinite Data Streams (or DPWEPP-IDS) is to release an obfuscated histogram r = [r 1 , r 2 , . . .] of D in each timestamp t achieving (t, wB,t , wF,t , E B,t , E F,t )-EPDP with the difference between r and c minimized where wB,t = [wB,1,t , . . . , wB,n,t ], E B,t = [EB,1,t , . . . , EB,n,t ], wF,t = [wF,1,t , . . . , wF,n,t ], E F,t = [EF,1,t , . . . , EF,n,t ]. Namely, min ϵθ

s.t.

X

∥r t − ct ∥22

t∈[T ] t X

ϵi,k ≤ EB,i,t ,

∀ui ∈ U

k=t−wB,i,t +1 t+wF,i,t −1

X

ϵi,k ≤ EF,i,t ,

∀ui ∈ U

k=t

where ϵi,k indicates the privacy budget cost at time slot k. 4 Personalized Window Size Mechanism In this section, we consider the fixed personalized setting, where each user maintains the same privacy requirement across all time slots. Although this setting is simpler than the dynamic case, it provides the core release components needed by our general framework. In particular, it allows us to introduce the basic mechanism for transforming heterogeneous budgets into a system-level release decision. We refer to this fixed problem as Dynamic Personalized w-Event Private Publishing for Infinite Data Streams (DPWEPP-IDS).

7

To maximize estimation accuracy at each time slot, we first analyze the reporting error and then introduce Optimal Budget Selection (OBS), a basic component for determining a release threshold under heterogeneous privacy budgets. Based on OBS, we develop the Personalized Window Size Mechanism (PWSM), which transforms heterogeneous personalized privacy requirements into a system-level release decision for the fixed personalized setting.

4.1 Problem Simplifying Definition 11 (PWEPP-IDS). Given a user set U = {u1 , u2 , . . ., un }, each ui holds a privacy requirement (wi , Ei ) and a series data xi,t for t ∈ N+ . All the xi,t for ui ∈ U at time slot t form Dt . All the Dt form an infinite data stream S = [D1 , D2 , . . .]. PWEPP-IDS is to publish an obfuscated histogram r = [r 1 , r 2 , . . .] of S at each time slot t achieving (w, E)-EPDP with the distance between r and c minimized, namely ∀T ∈ N+ : min ϵθ

s.t.

X

∥r t − ct ∥22

t∈[T ] t X

ϵi,τ ≤ Ei ,

∀ui ∈ U

τ =min (t−wi +1,1)

where ϵi,τ indicates the privacy budget cost at time slot τ .

Proposition 1 The fixed personalized setting is a special case of the dynamic personalized setting when, for every user ui and every time slot t, the privacy requirements remain constant over time. That is, (wB,i,t , EB,i,t , wF,i,t , EF,i,t ) reduce to fixed user-specific parameters (wi , Ei ). Moreover, when all users share the same fixed privacy requirement, the model further reduces to the classical homogeneous w-event setting. Proof (sketch). When privacy requirements do not vary over time, the dynamic feasibility constraints become fixed personalized budget constraints, and DPWEPP-IDS reduces to PWEPP-IDS. If all users further share the same privacy budget and event window, the personalized constraints collapse into a single homogeneous constraint, which recovers the classical w-event setting.

4.2 Reporting Errors Privacy budget allocation can be determined for any type of privacy requirement at each time slot. For time slot t with privacy budget allocation ϵ = {ϵ1 , . . . ϵn }, we use the Sampling Mechanism (SM) [24] to satisfy all users’ privacy requirements (i.e., achieving ϵ-PDP). SM operates in two

Leilei Du1 et al.

8

steps: sample (SMs ) and disturb (SMd ). In SMs , the server sets a privacy budget threshold ϵθ and constructs a sampling subset DS . Specifically, it adds items xi with ϵi ≥ ϵθ directly to DS , while sampling other items xi with ϵi < ϵθ ϵi at a probability of pi = eeϵθ −1 −1 . In SMd , the server uses a DP mechanism (e.g., the Laplace Mechanism) to generate an obfuscated result that achieves ϵθ -DP. SM introduces two types of errors: sampling error (errs ) and noise error (errdp ). Given a privacy budget threshold ϵθ , errs (ϵθ ) occurs when sampling users with privacy budgets below ϵθ , while errdp (ϵθ ) results from adding noise to achieve ϵθ -DP. The sum of these two errors constitutes the total reporting error. Next, we introduce these sampling and noise errors in detail. Definition 12 (Sampling Error [24]). Given a privacy budget threshold ϵθ and m distinct privacy budgets ϵ̃1 , ϵ̃2 , . . . , ϵ̃m from n users with ϵ̃i < ϵ̃j for  mi < j and  P i, j ∈ [m] where ϵ̃i is declared by ni users ni = n , i=1

the sampling error errs (ϵθ ) is defined as errs (ϵθ ) = Var(count(r t )) + bias(r t )2  2 X X  = ni pi (1 − pi ) + ni (1 − pi ) , ϵ̃i <ϵθ

ϵ̃i <ϵθ

eϵ̃i −1 ϵθ

where pi = e

−1 .

Definition 13 (Noise Error [24]). The noise error errdp (ϵθ ) is defined as the error of the Laplace mechanism, namely, errdp (ϵθ ) =

2 . ϵ2θ

Various metrics exist to measure the errors of Laplace mechanisms for noise error, including variance [24, 34], scale [25, 19], and (α, β)-usefulness [19, 5]. In this work, we employ variance as our metric. 4.3 Optimal Budget Selection Given the budget allocation (ϵ1,t , ϵ2,t , . . . , ϵn,t ) of n users, we can determine the frequency of each distinct budget and select the optimal ϵθ that minimizes the data reporting error err. This process is detailed in Algorithm 1. Taking n privacy budgets as input, the Optimal Budget Selection (OBS) algorithm first counts the distinct privacy budgets (Lines 1-2). It then finds the minimum reporting error errmin (lines 4-8). Specifically, it iterates through all distinct privacy budgets ϵ̃k ∈ ϵ̃ and identifies the value ϵ̃k that produces the smallest total error err = errs (ϵ̃k ) + errdp (ϵ̃k ). This value and its error are returned as the optimal privacy budget ϵopt and the minimum error errmin . Example 2 (Running Example of the OBS Algorithm) Suppose we have 10 privacy budgets as input: ϵ = (0.1,

Algorithm 1: Optimal Budget Selection (OBS) Input: personalized privacy budget list ϵ = (ϵ1 , ϵ2 , . . . , ϵn ) Output: ϵopt , errmin 1 Extract distinct budget set ϵ̃ = (ϵ̃1 , ϵ̃2 , . . . , ϵ̃ñ ) from ϵ; 2 Count the frequency nk of all ϵ̃k ∈ ϵ̃; 3 Initialize errmin as the upper bound of error value; 4 for ϵ̃k ∈ ϵ̃ do 5 err ← errs (ϵ̃k ) + errdp (ϵ̃k ); 6 if err < errmin then 7 errmin ← err; 8 ϵopt ← ϵ̃k ; 9

return ϵopt , errmin

0.4, 0.4, 0.1, 0.4, 0.4, 0.8, 0.8, 0.8, 0.4). OBS first determines ϵ̃ = (0.1, 0.4, 0.8), ñ = |ϵ̃| = 3, and N = (2, 5, 3). Based on these statistics, OBS iterates through the 3 privacy budgets in ϵ̃ and calculates their 0.1 2 errors: err1 = 0 + 0.1 = 200, err2 = 2 × ee0.4 −1 × 2 −1   2 0.1 2 2 × 1 − ee0.4 −1 + 0.4 = 15.31 and 2 −1     0.1 0.1 0.4 0.4 e −1 e −1 e −1 + err3 = 2× e0.8 −1 × 1 − e0.8 −1 +5× e0.8 −1 × 1 − ee0.8 −1 −1     2 e0.1 −1 e0.4 −1 2 2 × 1 − e0.8 −1 + 5 × 1 − e0.8 −1 + 0.82 = 89.74. Fi

0.1

−1 1 − ee0.4 −1



+

nally, OBS returns 0.4 with the minimum error 15.31.

4.4 Personalized Window Size Mechanism In real applications, to realize personalized privacy protection, the system need to get the collect users’ privacy requirements. To accomplish this, system administrators first define a discretized privacy budget range (e.g., {0.1, 0.5, 0.9}) and a window size range (e.g., {40, 80, 120}). Then, they map ascending privacy budget values to descending privacy budget levels (e.g., High, Medium, Low) and ascending window size values to ascending window size levels (e.g., Small, Medium, Large). Users can then select both a privacy budget level and a window size level based on their needs and past experience. Once users submit these selections, the server converts them into the corresponding values. After receiving all users’ privacy requirements, the system must determine how to allocate privacy budgets within each user’s feasible window while maximizing estimation accuracy. Classical budget-division methods [25, 34] are designed for homogeneous w-event privacy, where all users share the same privacy budget and the same event window. In our setting, however, users may specify different window sizes and privacy budgets, whereas the system still publishes one shared aggregate result at each time slot. Therefore, the key issue is no longer how to allocate a single global privacy budget sequence, but how to transform heterogeneous feasible budgets into a valid system-level release decision. To address this challenge, we propose the Personalized Window Size Mechanism (PWSM). The core

Personalized w-Event Privacy for Infinite Stream Estimation

idea is to use OBS together with the sampling mechanism to convert heterogeneous user-specific privacy budgets into a common release threshold, and then use that threshold to perform personalized dissimilarity estimation and adaptive release. Personalized Private Dissimilarity Measure. The personalized dissimilarity measure dis∗ is defined as the absolute error between the true statistic c̃t under SMs (i.e., the sample step of SM) at current time slot t and the last publication r l , namely,

9

Algorithm 2: Personalized Window Size Mechanism (PWSM) Input: historical estimation His, privacy requirement (wt , E t ) at time slot t Output: r 1 Calculate the current privacy budgets ϵt of all users according to E t and wt ; (1) 2 Split ϵt into two components: the calculation budget ϵt and (2)

(1)

(2)

the publication budget ϵt satisfying ϵt = ϵt + ϵt ; 3 Calculate dissimilarity dis between current estimation and the (1)

last estimation by SM(ϵt ); Calculate the reporting error err of current estimation by   (2) OBS ϵt ; √ 5 if dis > err then   (2) 6 Calculate current estimation r by SM ϵt ;

4

d

dis∗ =

1 X |c̃t [k] − r l [k]|. d k=1

Our goal is to privately obtain the personalized dissimilarity dis∗ using the optimal privacy budget ϵopt calculated through OBS algorithm. The personalized private dissimilarity measure dis is then defined as: dis = dis∗ + Lap



1 d · ϵopt

7 8 9

else Set current estimation r as the last reporting value; return r.

 ,

where Lap denotes the Laplace noise in the Laplace mechanism [19]. Based on the above observation, we introduce PWSM as a framework for unifying heterogeneous personalized privacy budgets into a shared release decision. As shown in Algorithm 2, the PWSM algorithm takes the historical estimation His and the current personalized privacy requirement (wt , E t ) as the input. PWSM first calculates all users’ budget allocations ϵt at the current time slot t on the premise of satisfying (wt , E t )-EPDP (line 1). It then divides ϵt into (1) two parts: calculation budget ϵt and publication budget (2) (1) ϵt (line 2). Using ϵt , PWSM calculates the personalized private dissimilarity dis between the current count value and the last reported one (line 3). Next, it sets the change thresh(2) old as the reporting error err calculated with ϵt (line 4). Finally, PWSM adaptively decides whether to publish a new obfuscated estimation or skip (i.e., use the last published one √ to approximate) by comparing dis to err (lines 5-9). Next, we present two methods based on PWSM: Personalized Budget Distribution (PBD) and Personalized Budget Absorption (PBA), each designed to handle different types of data streams.

4.5 Personalized Budget Distribution and Personalized Budget Absorption Basic notations. Before describing our personalized methods, we first need to declare some important notations specific to these methods. Definition 14 (Null/Non-null Publication). Given a sequence of publications (r1 , r2 , . . . , rt ), a null publication

refers to approximating a historical value without consuming any privacy budget in PartNOP , while a non-null publication represents a new publication that consumes privacy budget in PartNOP . For any time slot 2 ≤ τ ≤ t, we refer to rτ −1 as the last reporting value (or last publication) of time slot τ . In the sequence (r1 , r2 , . . . , rτ ), we define the most recent non-null publication rl where l < τ as the last non-null publication. For example in Figure 2, the publications at time slots τ, τ + 1, τ + 4 are non-null publications, while those at τ + 2 and τ +3 are null publications. The last non-null publication at time slot τ + 4 is the publication at time slot τ + 1.

Fig. 2: A null/non-null publication example.

Definition 15 (Skipped/Nullified Publication). The skipped √ publications are those null publications with dis ≤ err. Given a privacy budget requirement E and a window size w, a budget share ϵ̄ = E/w is defined as the average privacy budget per time slot. When publishing new obfuscated data consumes x budget shares (x > 1), in order to maintain the average value, the following x − 1 time slots values are approximated by the last publications. These x−1 time slots are defined as nullified time slots. We can see both skipped and nullified publications are non publications. Figure 3 illustrates an example for skipped and nullified publications. With a privacy budget E of 4 and

Leilei Du1 et al.

10

Fig. 3: A skipped/nullified publication example.

Algorithm 3: Dissimilarity Calculation (DC) Input: Dt , current personalized privacy budget list ϵt , historical data publication (r 1 , r 2 , . . . , r t−1 ) Output: r t 1 ϵopt ← OBS(ϵt ) ; 2 D̃t ← SMs (Dt , ϵt , ϵopt ); 3 c̃t ← Q(D̃t ); 4 Get the last non-null publication r l from (r 1 , r 2 , . . . , r t−1 ); 1 Pd 5 return dis ← j=1 |c̃t [j] − r l [j]| + Lap(1/(d · ϵopt )); d

Algorithm 4: Personalized Budget Distribution (PBD) Input: Dt , privacy requirement set (w, E), historical data publication (r 1 , r 2 , . . . , r t−1 ) Output: r t 1 Calculate the current window average budget ϵ̄i ← Ei /wi for each i ∈ [n]; (1) 2 Set ϵt ← (ϵ̄1 /2, ϵ̄2 /2, . . . , ϵ̄n /2);   (1) 3 dis ← DC Dt , ϵt , r 1 , r 2 , . . . , r t−1 by Algorithm 3; Pt−1 (2) 4 Set ϵrm,i ← Ei /2 − k=t−wi +1 ϵi,k for each i ∈ [n]; (2)

← (ϵrm,1 /2, ϵrm,2 /2, . . . , ϵrm,n /2);   (2) (2) (2) ϵopt , erropt ← OBS ϵt by Algorithm 1; q (2) erropt then 7 if dis >   (2) (2) (2) 8 D̃t ← SMs Dt , ϵt , ϵopt ;   (2) (2) ; 9 c̃t ← Q D̃t   (2) (2) 10 return r t ← SMd c̃t , ϵopt ; 5

ϵt

6

11 12 13

else (2)

ϵt ← (0, 0, . . . , 0); return r t ← r t−1 ;

a window size of 4, the budget share ϵ̄ equals E/w = 1. When time slot τ + 1 uses 3 shares, the publications at time slots τ + 2 and τ + 3 become nullified publications. Personalized Budget Distribution (PBD). As shown in Algorithm 4, PBD inputs the current user data, all users’ fixed privacy requirements, and historical data publication. The fixed privacy budget requirement Ei of ui is split into two parts: 1) PartDC for calculating the dissimilarity between the current data and the last publication (Lines 2-3); 2) PartNOP for calculating the new obfuscated publication at the current time slot (Lines 4-6 and Lines 8-10). In PartDC , we allocate half of the average privacy budget Ei for ui ). per time slot for dissimilarity calculation (i.e., 2w i The process then calls the Dissimilarity Calculation (Algo-

Fig. 4: An Information example for PBD.

rithm 3) to determine the dissimilarity. Within Algorithm 3, the OBS algorithm selects the optimal budget threshold ϵopt . Finally, it uses the SM [24] to compute the dissimilarity dis (Lines 2-5). Notice that the remaining budget calculation in Line 4 is a standard sliding-window sum and can be maintained incrementally. In PartNOP , we first calculate the remaining privacy budget ϵrm,i for each ui . We then set the publication privacy budget for each ui to half of ϵrm,i . Similar to dissimilarity calculation, we use the OBS algorithm to determine the optimal (2) (2) privacy budget ϵopt and its corresponding error erropt . At this point, we have obtained two measurements: the dissimilarity q (2)

dis and the square root of error erropt . We compare these two measurements to determine whether to publish a new obfuscated statistic result or approximate the current q result (2)

with the last publication. If the dis is greater than erropt , it indicates that the difference between the current data and the last published data exceeds the error of noise, then we republish a new obfuscated statistic result. Otherwise, we take the last publication instead. Example 3 Suppose there are 3 users distributed across 5 locations, forming a complete graph. Figure 4 illustrates the fixed personalized privacy requirements and locations for the first three users across time slots 1 to 5. Figure 5 demonstrates the estimation process of PBD. The total privacy budget for each user ui is evenly split into two parts, each containing Ei /2. The first part is allocated for dissimilarity calculation, while the second is for publication noise calcula(1) tion. For instance, E1 is divided into ϵ1 (u1 ) = E1 /2 and (2) (1) ϵ1 (u1 ) = E1 /2. We compute the privacy budget usage ϵi,t (2)

for dissimilarity and ϵi,t for obfuscated statistic publication for each user at each time slot. These values are recorded in an n × 2 matrix at each time slot in Figure 5. Using u1 (1) (1) as an example, ϵ1,t = ϵ1 (u1 )/w1 = E1 /8. At time slot (2)

(2)

1, ϵ1,1 = ϵ1 (u1 )/2 = E1 /4. The algorithm calculates the (1)

dissimilarity dis at time slot 1 using all ϵi,1 , and the error q (2) (2) (2) erropt using all ϵi,1 . Assume dis > erropt , then a new obfuscated statistic q r 1 is published at time slot 1. At time slot (2)

(2)

2, assume dis ≤ erropt , then ϵi,2 is not used to publish a new obfuscated statistic result, and its usage is set to zeros

Personalized w-Event Privacy for Infinite Stream Estimation

11

Algorithm 5: Personalized Budget Absorption (PBA) Input: Dt , fixed personalized privacy requirement set (w, E), historical data publication (r 1 , r 2 , . . . , r t−1 ) Output: r t 1 Calculate the current window average budget ϵ̄i = Ei /wi for each i ∈ [n]; (1) 2 ϵt ← (ϵ̄1 /2, ϵ̄2 /2, . . . , ϵ̄n /2);   (1) 3 dis ← DC Dt , ϵt , r 1 , r 2 , . . . , r t−1 by Algorithm 3; 4 5

for i ∈ [n] do Initialize nullified time slots ti,N as 0; ϵ

(2)

i,l Set ti,N ← E /(2w − 1 if l exists where l is the last i i) non-null publication time slot;

6

Set nullified time slot bound t̃N ← maxi∈[n] ti,N ; if t − l ≤ t̃N then 9 return r t ← r t−1 ;

7

8

10

Fig. 5: A process example for PBD. (2)

19 20

else

12

(2)

for all users. At time slot 3, ϵ1,3 = (E1 /2 − ϵ1,1 )/2 = E1 /8. The vector below each matrix in Figure 5 represents the total privacy budget used at the current time slot for each user. For example, at time slot 1, the total privacy budget usage (1) (2) for u1 is ϵ1,1 + ϵ1,1 = 3E1 /8. Personalized Budget Absorption (PBA). Algorithm 5 outlines the process of PBA. The dissimilarity calculation (PartDC ) in PBA is identical to that of PBD. However, PBA and PBD differ significantly in their strategies on allocating the publication privacy budget (PartNOP ). For PartNOP in PBA, we assume an average privacy budEi (one share) for each ui at each time slot t. A get of 2w i publication at time slot t can use more than one share by borrowing from its successor time slots. The variable ti,N in Line 6 represents the number of successor time slots occupied by the last publication. We calculate the maximal t̃N of all ti,N and determine whether the current time has been occupied (t − l ≤ t̃N ). If so, we approximate the publication using the last publication. Otherwise, we calculate the remaining budget shares from the precursor time slots (i.e., tA,i in Line 12) and set the current publication budget as the total absorbed shares (Line 13). The subsequent steps follow the same process as outlined in Algorithm 4. Example 4 We continue use the demonstration case shown in Figure 4. Figure 6 illustrates the estimation process of PBA. The dissimilarity calculation process in PBA is identical to that in Example 3. For PartNOP , at time slot 1, with no budget to absorb, all users utilize one share (i.e., Ei /(2wi )) to publish a new obfuscated statistic result. As  q

sume time slot 2 is skipped i.e., dis ≤ err(2) opt . At time slot 3, t1,N = t2,N = t3,N = 0. Thus, the nullified bound t̃N is 0. Since t − l = 3 − 1 = 2 > t̃N , a new obfuscated statistic result is reported. The publication budget set

else for i ∈ [n] do Set absorbed time slots tA,i ← max (t − l − ti,N , 0); (2) Ei Set publication budget ϵi,t ← 2w · min (tA,i , wi ); i   (2) (2) (2) (2) ϵt ← ϵ1,t , ϵ2,t , . . . , ϵn,t ;   (2) (2) (2) ; ϵopt , erropt ← OBS ϵt q (2) if dis > erropt then   (2) (2) (2) D̃t ← SMs Dt , ϵt , ϵopt ;   (2) (2) c̃t ← Q D̃t ;   (2) (2) return r t ← SMd c̃t , ϵopt ;

11

13 14 15 16 17 18

21 22

(2)

ϵt ← (0, 0, . . . , 0); return r t ← r t−1 ;

(2)

is calculated as ϵ3 = (E1 /4, E2 /2, E3 /3). At time slot 4, t1,N = t2,N = t3,N = 1. As t − l = 4 − 3 = 1 ≤ t̃N , the publication is approximated as the one at time slot 3. At time slot 5, all ti,N remain 1, and t − l = 5 − 3 = 2 > t̃N . The absorbed time slots tA,i all equal 1. The publication budget (2) set is ϵ5 = (E1 /8, E2 /4, E3 /6).

4.6 Analyses Time Cost Analysis. Let m be the number of distinct privacy requirements (wi , Ei ), where m ≤ n. Then we have Theorem 1 as follows. Theorem 1 The time complexities of PBD and PBA are both O(n). Proof The time complexity of OBS is O(m) for both PBD and PBA. The Sample Mechanism and Query operations each have a time complexity of O(n). Thus, the time complexities of PBD and PBA both are O(n).

Leilei Du1 et al.

12

of size wL . We also assume there is no budget absorption from past time slots outside the window. Furthermore, for each user, each publication approximates the same number of skipped or nullified publications. We first present a crucial lemma. Lemma 1 Given m distinctPprivacy budget-quantity pairs P = (ϵj , nj )|j ∈ [m], j∈[m] nj = n where pair (ϵj , nj ) indicates that ϵj appears nj times in the user privacy requirement, and a query with sensitivity I, the error f O (P ) of the SM process with privacy budupper bound err get chosen from OBS is: !   2I 2 1 2I 2 , (n − nA ) n − nA + , + minj ϵ2j 4 maxj ϵ2j

min

(3)

where nA = nk with k = arg maxj∈[m] ϵj . Fig. 6: A process example for PBA.

Memory Complexity Analysis. For PBD and PBA, we have Theorem 2 as follows. Theorem 2 Both PBD and PBA have memory complexity O(n · wmax ). Proof For the process of OBS, the memory complexity is O(m). For each one of the n users in both PBD and PBA, each user requires storing at most wmax window-related states. Thus, the memory complexity is O(n · wmax ). Scalability Discussion. The above time and memory bounds indicate that PBD and PBA are scalable to large user populations. At each time slot, the computation only requires processing the current per-user privacy requirements and maintaining a limited amount of historical state within the relevant window(s), rather than revisiting the entire stream history. Therefore, the per-time-slot cost grows linearly with the number of users n, while the memory usage is bounded by the maintained budget/publication states associated with active windows. This makes the method practical for long-running streams with a large user population, provided that the maximum window size remains moderate. Privacy Analysis. As for the privacy analysis of PBD and PBA, we have Theorem 3 as follows. Theorem 3 PBD and PBA satisfy (w, E)-EPDP. Proof Please refer to details of Theorem 3 in Appendix 8.4.1. Utility Analysis. For each user ui in PBD and PBA, we define wL as the smallest window size among all users. Ei For each ui , given (wi , Ei ), let ϵL = mini∈[n] w and i Ei ϵR = maxi∈[n] wi be the minimum and maximum values of Ei wi , respectively. Let nA be the number of times ϵR appears among all users. We assume that at most s̃ ≤ wL non-null publications occur at time slots q1 , q2 ,. . . , qs̃ in the window

Proof Let ML be the SM with privacy budget chosen as minj ϵj . According to the SM process, all budget types will be selected. In this case, the sampling error errs is 0 and the  2 2I 2 noise error errdp is 2 · minIj ϵj = min 2 . Thus, the total j ϵ j

2

2I error of ML is errML = min 2 . Let MR be the SM with prij ϵ j

vacy budget chosen as maxj ϵj . In this case, (m−1) types of eϵk −1 privacy budget are chosen with probability pk = emax j ϵj −1 less than 1 (k ∈ [m]). For the sampling error, we have: 2  errs =

X



X

nk

ϵk <maxj ϵj

nk (1 − pk )

ϵk <maxj ϵj

ϵk <maxj ϵj

<

X

nk pk (1 − pk ) + 

pk + 1 − p k 2

2

2

 +

X

nk 

ϵk <maxj ϵj

1 2 (n − nA ) + (n − nA ) 4   1 = (n − nA ) n − nA + . 4 =

The noise error errdp in this case is 2 ·



I maxj ϵj

2

=

2I 2 . Thus, the total error of MR is errMR = (n − maxj ϵ2j
2I 2 nM ) n − nM + 41 + max 2 . According to the OBS proj ϵj

f O (P ) ≤ errML and err f O (P ) ≤ errMR . cess, we have err Therefore, ef rrO (P ) ≤ min (errML , errMR ) = min

2I 2 , (n − nM ) minj ϵ2j

 n − nM +

1 4

 +

2I 2 maxj ϵ2j

! .

To ensure the robustness of Lemma 1, we analyze the behavior of the proposed mechanism under extreme conditions. Specifically, we consider two extreme cases: (1) Uniform Privacy Budget. When all users possess the same privacy budget, i.e., ϵj ≡ ϵ, the system reduces to a single budget-quantity pair (ϵ, n). Here, the error equals the standard CDP bound, i.e., 2I 2 /ϵ2 . Given nM = n, Equation (3)  2

2

2

2I evaluates to min 2I = 2I ϵ2 , 0 + ϵ2 ϵ2 . Thus, the equation consistently recovers the standard CDP error in the uniform setting; (2) Highly Disparate Privacy Budgets. When

Personalized w-Event Privacy for Infinite Stream Estimation

13

some users have significantly larger privacy budget than others (e.g., ϵ1 ≪ ϵ2 ≪ · · · ≪ ϵn ), the error is no more than 2I 2 / minj ϵ2j , which is exactly the dominant error term errML in Equation (3). Thus, Lemma 1 still holds in these two extreme cases. For PBD we present Theorem 4 to declare its error upper bound as follows. Theorem4 The averageerror per slot in PBD is at  time  s̃ s̃ −1) −1) most min d28ϵL , Z + d28ϵR +min 32·(4 , Z + 32·(4 3s̃ϵL 3s̃ϵR
where Z = (n − nA ) n − nA + 14 , if at most s̃ non-null publications occur in any window with size wL . Proof Please refer to details of Theorem 4 in Appendix 8.5.1. PBD achieves low error when the number of non-null publications s̃ per window is small. However, the error increases exponentially with s̃. Additionally, the error in PartDC (the first part of the error upper bound in PBD) rises as wL increases, however, it diminishes as d increases. This is because a large d reduces sensitivity leading to smaller noise error. For PBA, assume α skipped publications occur before a publication. Let ϵL̃ and ϵR̃ be the minimum and maximum publication privacy budgets among all users at time slots t = wL and t = (α + 1), respectively. According to the PBA process, there will be α nullified publications after the publication. These nullified publications are set as the last non-null publication without comparison. Consequently, the nullified publication error depends on the data distribution at nullified time slots. We denote the average error of each nullified publication in PBA as errnlf . For PBA, we have Theorem 5 as follows. Theorem 5 The  average error  per time  slot in PBA is  (s,p) 1 at most min d28ϵL , Z + d28ϵR + 2α+1 ef rrNOP + α · errnlf (s,p)

where ef rrNOP is min α ≤ wL and min  1) min

2 , Z + ϵ22 ϵ2 L̃







2 2 2 Hα+1 , (α + 1)Z + ϵ22 Hα+1 ϵ2L R

2 2 2 Hw , wL Z + ϵ22 Hw L L ϵ2L R





when

+ (α − wL +

when α > wL and Z = (n −

R̃

and Hx2 is the x-th square harmonic number, if there are α skipped publications occur in average before each publication. nA )

n − nA + 14

Proof Please refer to details of Theorem 5 in Appendix 8.5.2. Discussion on Frequent-Update Regimes. The bound above shows that the utility of PBA may deteriorate when the number of skipped and nullified publications becomes large. This does not weaken the formal privacy guarantee of PBA, which is still ensured by the budget-composition analysis in Theorem 3, but it may reduce estimation accuracy when the stream changes too frequently. Therefore,

PBA is more suitable for relatively smooth streams, whereas PBD is preferable when the stream exhibits persistent rapid changes. 5 Dynamic Personalized Window Size Mechanism In this section, we consider the dynamic personalized setting, where each user may specify different backward and forward privacy requirements at different time slots. Unlike the fixed setting, the privacy budget allocation at the current time slot cannot be determined solely from the current requirement. Instead, it must remain consistent with previously consumed privacy budgets and, at the same time, preserve feasibility for future privacy requirements. Therefore, the dynamic setting introduces an online feasibility problem under heterogeneous time-varying personalized privacy requirements. To address this problem, we generalize the fixed-setting framework to a dynamic framework called Dynamic Personalized Window Size Mechanism (DPWSM). DPWSM focuses on online feasibility maintenance and shared releasebudget construction under dynamic personalized privacy requirements, rather than merely substituting personalized parameters into existing w-event mechanisms. The key idea of DPWSM is to compute feasible privacy budget upper bounds at each time slot under both backward and forward privacy requirements, and then use these feasible budgets to make a shared release decision for the current time slot. 5.1 Feasibility Conditions for Privacy Budget Requirements Backward Feasibility Condition. At time slot t, user ui may declare a desired backward privacy requirement (wB,i,t , EB,i,t ). Since the historical privacy budget consumption {ϵi,k }k<t is maintained internally by the trusted curator, the feasibility of this declared backward budget is checked by the curator rather than by the user. A backward requirement is feasible only if 0 ≤ ϵi,t ≤ EB,i,t −

t−1 X

ϵi,k for i ∈ [n].

k=max (t−wB,i,t +1,1)

If the declared backward budget is infeasible, the curator either rejects it or projects it to the minimal feasible value before computing the current release budget. The backward feasibility condition has two parts. The first rule requires users to propose valid backward privacy budgets that exceed their historical privacy usage within the current backward window. We assume the trusted curator enforces this feasibility condition before budget allocation at each time slot. The second rule establishes an upper bound for each user’s privacy budget usage at the current time slot.

Leilei Du1 et al.

14

Forward Feasibility Condition. Let TB,i,t = {τ |τ ≤ t ≤ τ + wF,i,τ − 1} be the set of backward time slots whose forward windows cover time slot t. The privacy budget usage ϵi,t must not exceed the minimal remaining forward privacy budget among all the time slots in TB,i,t . Namely, 0 ≤ ϵi,t ≤

min

τ ∈TB,i,t

EF,i,τ −

t−1 X

! ϵi,k

for i ∈ [n].

k=τ

The forward feasibility condition ensures that the privacy budget usage at the current time slot does not violate the forward privacy requirements of all historical time slots. We illustrate this forward feasibility condition in Example 5.

Fig. 7: An example for the forward feasibility condition.

Example 5 As shown in Figure 7, assume ui spends privacy budgets ϵi,1 , ϵi,2 and ϵi,3 at time slots t1 , t2 and t3 , respectively. The forward window sizes of ui at these time slots (k) are 5, 2 and 4. Let ϵi,j represent ui ’s upper bound of the budget usage at time slot tj constrained by the forward budget requirement at tk . Based on the requirement at t1 , for the P3 (1) budget usage at t4 , we have ϵi,4 ≤ EF,i,1 − k=1 ϵi,k . Since the forward window at t2 does not cover t4 , its requirement does not affect ϵi,4 . Based on the requirement at t3 , for the P3 (3) budget usage at t4 , we have ϵi,4 ≤ EF,i,3 − k=3 ϵi,k = EF,i,3 − ϵi,3 . Therefore,  the final budget upper bound is (1)

(3)

ϵi,4 = min ϵi,4 , ϵi,4 .

5.2 Solution for DPWEPP-IDS In this subsection, we instantiate DPWSM with two mechanisms: Dynamic Personalized Budget Distribution (DPBD) and Dynamic Personalized Budget Absorption (DPBA). Both mechanisms follow the same feasibility principle: the privacy budget used at each time slot must satisfy both backward and forward personalized privacy requirements. They differ in how the feasible publication budget is scheduled across time slots: DPBD follows a distribution-based strategy, whereas DPBA follows an absorption-based strategy. Dynamic Personalized Budget Distribution. DPBD extends PBD to satisfy users’ variable privacy level demands at different time slots. Similar to PBD, the process in DPBD is divided into PartDC for dissimilarity calculation and PartNOP for publication calculation.

To satisfy both backward and forward feasibility conditions, the privacy budget usages in PartDC and PartNOP are required to comply with these feasibility conditions using half of the backward and forward privacy (1) budgets. Specifically, for PartDC : ϵi,t ≤ EB,i,t /2 − Pt−1 (1) (backward feasibility condition), k=max(t−wB,i,t +1,1) ϵi,k  Pt−1 (1)  (1) and ϵi,t ≤ minτ ∈TB,i,t EF,i,τ /2 − k=τ ϵi,k (forward (2)

feasibility condition). For PartNOP : ϵi,t ≤ EB,i,t /2 − Pt−1 (2) (backward feasibility condition), k=max(t−wB,i,t +1,1) ϵi,k  Pt−1 (2)  (2) and ϵi,t ≤ minτ ∈TB,i,t EF,i,τ /2 − k=τ ϵi,k (forward feasibility condition). The process of DPBD is shown in Algorithm 6. For each user ui , we obtain the historical time slot set TB,i,t where each elmement’s forward window covers the current time slot (Line 2). In PartDC process, for each historical time slot τ , the total forward privacy budget is set as EF,i,τ /2 and allocated evently among all the time slot within the forward window. Thus each time slot in the forward window with size wF,i,τ holds forward privacy budget as EF,i,τ /(2wF,i,τ ). Therefore, the privacy budget upper bound based on the forward E feasibility condition at time slot t is minτ ∈TB,i,t 2wF,i,τ F,i,τ (Line 3). Based on the backward feasibility condition, the privacy budget upper bound at time slot t is set as Pt−1 (1) EB,i,t /2 − τ =t−wB,i,t +1 ϵi,τ (Line 4). To satisfy both feasibility conditions, each user ui ’s budget usage for PartDC (1) is set to the minimum of these two upper bounds: ϵi,t =   (1) (1) min ϵF,i,t , ϵB,i,t (Line 5). The subsequent steps in PartDC follow Algorithm 4 (PBD). (2)

In PartNOP process, the forward remaining budget ϵF,i,t for each ui is set to half of the minimum forward remaining budgets across all time slots in TB,i,t (Line 9). The back(2) ward remaining budget ϵB,i,t for each ui is set to the remaining budget within the front wB,i,t time slots. The final publication budget for each ui is determined by taking the (2) (2) minimum value between ϵF,i,t and ϵB,i,t . The subsequent steps in PartNOP follow those in Algorithm 4 (PBD). Example 6 Consider a system with users’ privacy requirements shown in Table 3. Privacy requirements are denoted as B : (a, b) and F : (c, d), where a is the backward window size wB,i,t , b is the backward privacy budget EB,i,t , c is the forward window size wF,i,t , and d is the forward privacy budget EF,i,t . We analyze the first 5 time slots with privacy settings shown in Figure 8. The status is recorded i h (1) (2) (2) (1) as ϵB,i,t , ϵF,i,t ; ϵB,i,t , ϵF,i,t with non-null publications occuring at time slots t = 1 and t = 3. At each time slot, we first compute the calculation budgets by Lines 2-5 of Algorithm 6, and then compute the publication budgets by

Personalized w-Event Privacy for Infinite Stream Estimation

Algorithm 6: Dynamic Personalized Budget Distribution (DPBD) Input: Dt , dynamic personalized privacy requirement set (wB,t , E B,t , wF,t , E F,t ), historical data publication (r 1 , r 2 , . . . , r t−1 ) Output: r t 1 for i ∈ [n] do 2 Calculate TB,i,t ← {τ |τ ≤ t ≤ τ + wF,i,τ − 1};

15

13 in Algorithm 4, there is no new publication occurs at this time slot. Thus, the publication budget usage is 0. The budgets for the remaining three time slots are also recorded in Figure 8.

E

(1)

Calculate ϵF,i,t ← minτ ∈TB,i,t 2wF,i,τ ; F,i,τ P (1) (1) 4 Calcualte ϵB,i,t ← EB,i,t /2 − t−1 τ =t−wB,i,t +1 ϵi,τ ;   (1) (1) (1) 5 Set ϵi,t ← min ϵF,i,t , ϵB,i,t ;   (1) (1) (1) (1) 6 ϵt ← ϵ1,t , ϵ2,t , . . . , ϵn,t ;   (1) 7 Estimate dis ← DC Dt , ϵt , r 1 , r 2 , . . . , r t−1 by Algorithm 3; 8 for i ∈ [n] do 9 Calculate   P (2) (2) ϵF,i,t ← 12 minτ ∈TB,i,t EF,i,τ /2 − t−1 k=τ ϵi,k ; 3

Calculate

10

  P (2) (2) ϵB,i,t ← EB,i,t /2 − t−1 τ =t−wB,i,t +1 ϵi,τ ;   (2) (2) (2) 11 Set ϵi,t ← min ϵF,i,t , ϵB,i,t ;   (2) (2) (2) (2) 12 ϵt ← ϵ1,t , ϵ2,t , . . . , ϵn,t ; 13

Same as Lines 6-13 in Algorithm 4

Fig. 8: An example for DPBD

Table 3: Privacy requirements in DPBD, where B and F denote backward privacy requirements and forward privacy budget requirements. Time u1 u2 u3

1 B : (1, 1.0) F : (4, 2.4) B : (1, 0.6) F : (2, 1.6) B : (1, 2.0) F : (3, 1.2)

2 B : (2, 2.4) F : (4, 3.2) B : (2, 1.6) F : (2, 2.4) B : (2, 1.2) F : (3, 3.0)

3 B : (2, 2.8) F : (3, 4.2) B : (2, 3.2) F : (2, 2.8) B : (3, 1.8) F : (2, 1.2)

4 B : (2, 2.4) F : (3, 2.4) B : (3, 4.2) F : (2, 2.8) B : (2, 3.2) F : (3, 0.6)

5 B : (5, 3.0) F : (2, 0.8) B : (3, 3.6) F : (2, 2.0) B : (4, 2.4) F : (3, 1.8)

Lines 9-11. Finally, the release decision follows Line 13 of Algorithm 6 together with Lines 6-13 of Algorithm 4. At time slot 1, for u1 , the forward and backward privacy (1) (1) 2.4 budgets in PartDC are ϵF,1,1 = 2×4 = 0.3 and ϵB,1,1 = 1.0 2 = 0.5 according to Lines 2-4. The calculation budget is (1) therefore ϵ1,1 = min (0.5, 0.3) = 0.3 in Line 5. In PartNOP , (2)

the forward and backward budgets are ϵF,1,1 = 2.4 2 /2 = 0.6 (2)

and ϵB,1,1 = 1.0 2 = 0.5 according to Lines 9 and 10. Thus, (2)

the publication budget is ϵ1,1 = min (0.5, 0.6) = 0.5 in Line 11. The backward and forward budgets in PartDC and PartNOP are recorded as [0.5, 0.3; 0.5, 0.6], while the calculation and publication budgets are recorded as [0.3; 0.5]. The budgets for u2 and u3 are shown below u1 ’s. At time slot 2, take u1 as an example, the forward (1) and backward privacy budgets in PartDC are ϵF,1,2 =   (1) 3.2 min 2×4 , 0.3 = 0.3 and ϵB,1,2 = 2.4 2 − 0.3 = 0.9 (according to Lines 2-4). The calculation budget is therefore (1) ϵ1,2 = min (0.9, 0.3) = 0.3 in Line 5. According to the comparison in Line 13 in Algorithm 6 together with Lines 6-

Dynamic Personalized Budget Absorption. DPBA enhances PBA by supporting dynamic privacy requirements for users. Similar to DPBD, DPBA consists of two submechanisms: PartDC and PartNOP . The private dissimilarity calculation in PartDC remains identical to DPBD. In PartNOP , the system determines whether to nullify the current time slot t for each user ui based on publication budget usage at the relevant historical publication time slots. For each historical time slot τ ∈ TB,i,t influencing time slot t, we calculate the nullified right time  slot border tFN,i,τ with totalpubliEF,i,τ cation budget shares where one share equals 2w F,i,τ

from

τ to (t − 1) (Line 7). For user ui at time slot t, we determine the final forward nullified time slot right border RFN,i as the maximum value of these time slot borders (Line 8). We then obtain the forward nullified right border R̃FN as the maximum value among all RFN,i (Line 11). If the current time slot t is no larger than R̃FN , t is nullified and skipped. Otherwise, for each ui , we calculate the budget absorption ϵAF,i,t as the maximum absorption budgets among all historically influencing time slots (Line 16). We also determine the minimum remaining forward budgets ϵUF,i,t across all historical time slots as the remaining forward budget upper bound (Line 17). The forward absorption budget ϵFA,i,t is set as the minimum between ϵAF,i,t and ϵUF,i,t (Lines 1618). Finally, we calculate the backward budget upper bound ϵUB,i,t (Line 19) and set the publication budget as the minimum between ϵFA,i,t and ϵUB,i,t (Line 20). The subsequent steps follow those in PBD.

Leilei Du1 et al.

16

Algorithm 7: Dynamic Personalized Budget Absorption (DPBA) Input: Dt , dynamic personalized privacy requirement set (wB,1,t , E B,t , wF,t , E F,t ), historical data publication (r 1 , r 2 , . . . , r t−1 ) Output: r t 1 for i ∈ [n] do 2 Calculate TB,i,t ← {τ |τ ≤ t ≤ τ + wF,i,τ − 1}; E

(1)

Calculate ϵF,i,t ← minτ ∈TB,i,t 2wF,i,τ ; F,i,τ P (1) (1) Calcualte ϵB,i,t ← EB,i,t /2 − t−1 τ =t−wB,i,t +1 ϵi,τ ;   (1) (1) (1) Set ϵi,t ← min ϵF,i,t , ϵB,i,t ;

3 4 5

for τ ∈ TB,i,t do Calculate ui ’s forward nullified time slot right border

6 7

(2)

Pt−1

from τ as tFN,i,τ ← E

µ=τ

ϵi,µ

F,i,τ /(2·wF,i,τ )

+τ −1

Set ui ’s forward nullified time slot right border as RFN,i ← maxτ ∈TB,i,t tFN,i,τ ;   (1) (1) (1) (1) 9 ϵt ← ϵ1,t , ϵ2,t , . . . , ϵn,t ;   (1) 10 Estimate dis ← DC Dt , ϵt , r 1 , r 2 , . . . , r t−1 by Algorithm 3; 11 Set forward nullified right border R̃FN ← maxi∈[n] RFN,i ; 12 if t ≤ R̃FN then 13 return r t ← r t−1 ; 8

14 15 16

else for i ∈ [n] do Calcualte allocated forward absorption budget   E (t − tFN,i,τ ) · 2·wF,i,τ ; ϵAF,i,t ← max τ ∈TB,i,t

17

τ ∈TB,i,t

18 19

20

F,i,τ

Calculate remaining forward budget upper bound ! t−1 P (2) EF,i,τ ϵUF,i,t ← min − ϵi,µ ; 2 µ=τ

Set forward absorption budget ϵFA,i,t ← min (ϵAF,i,t , ϵUF,i,t ); Calculate remaining backward budget upper bound P (2) ϵUB,i,t ← EB,i,t /2 − t−1 τ =t−wB,i,t +1 ϵi,τ ; Set publication budget

backward remaining budgets ϵUB,i,1 of 0.5, 0.3 and 1.0 for u1 , u2 and u3 respectively in Line 19, their final publication budgets are 0.3, 0.3, and 0.2 according Line 20. At time slot 2, the publication is skipped, resulting in 0 publication budget usage for all users in Line 22 together with Lines 15-22 in Algorithm 5. At time slot 3, following Line 2, TB,1,3 = {1, 2, 3} for u1 . The forward nullified n time slot right border for each 0 0 time slot in TB,1,3 is 0.3 0.3 + 1 − 1, 0.4 + 2 − 1, 0.7 + o 3 − 1 = {1, 1, 2} according to Line 7. This yields an allocated forward absorption budget of ϵAF,1,3 = max((3 − 1) × 0.3, (3 − 1) × 0.4, (3 − 2) × 0.7) = 0.8 in Line 16. For u2 and u3 , we calculate ϵAF,2,3 = 1.2 and ϵAF,3,3 = 0.6. The remaining forward
budget upper bounds are ϵUF,1,3 = 3.2 4.2 min 2.4 = 0.9 for u1 , ϵUF,2,3 = 1.2 2 − 0.3, 2 , 2 for u2 , and ϵUF,3,3 = 1.2 for u3 according to Line 17. This results in forward absorption budgets of ϵFA,1,3 = min (0.8, 0.9) = 0.8, ϵFA,2,3 = min (1.2, 1.2) = 1.2, and ϵUF,3,3 = min (0.6, 1.2) = 0.6 in Line 18. The remaining backward budget upper bounds are ϵUB,1,3 = 2.8 2 = 1.4, 1.8 ϵUB,2,3 = 3.2 = 1.6, and ϵ = − 0.2 = 0.7 in UB,3,3 2 2 Line 19, leading to final publication budgets of 0.8, 1.2 and 0.6 for u1 , u2 , and u3 respectively in Line 20. At time slot 4, according to Line 8, we calculate the forward nullified time slot right borders as RFN,1 = 3.67, RFN,2 = 3.71 and RFN,3 = 4. Since the current time slot t = 4 ≤ R̃FN = max(3.67, 3.71, 4), following Lines 12-13, the publication is nullified, resulting in 0 publication budget usage for all users. At time slot 5, following the same process as time slot 3, we obtain publication budget usage of 0.4, 0.6 and 0.3 for u1 , u2 , and u3 in Line 20.

(2)

21

ϵi,t ← min (ϵFA,i,t , ϵUB,i,t );   (2) (2) (2) (2) ϵt ← ϵ1,t , ϵ2,t , . . . , ϵn,t ;

22

Same as Lines 15-22 in Algorithm 5

Example 7 Figure 9 illustrates the execution of DPBA. At each time slot, we first compute the candidate forward window set and the calculation budgets by Lines 2-5 of Algorithm 7. Then, the forward nullified right border is computed by Lines 6-8. If t ≤ R̃FN , the publication is nullified according to Line 13; otherwise, we compute the forward absorption budget, the remaining backward budget upper bounds, and the final publication budget by Lines 15-20. At time slot 1, TB,i,1 for each ui contains only the current time slot, resulting in RFN,i = 0 for all ui . Following Lines 16-18 of Algorithm 7, for u1 , we calculate E E 2.4 ϵAF,1,1 = 2wF,1,1 = 2×4 = 0.3 and ϵUF,1,1 = F,1,1 = 1.2, 2 F,i,1 leading to a forward absorption budget of ϵFA,1,1 = 0.3. For u2 and u3 , we obtain ϵFA,2,1 = 0.4 and ϵFA,3,1 = 0.2. With

Fig. 9: An example for DPBA

Personalized w-Event Privacy for Infinite Stream Estimation

17

5.3 Analysis In this subsection, we analyze the time cost and privacy levels of our DPBD and DPBA. Time Cost Analysis. For the time cost of DPBD and DPBA, we have Theorem 6 as follows. Theorem of DPBD and DPBA are 6 The time complexities   (F ) (B) both O wmax + wmax · n . Proof For each ui ’s TB,i,t at time slot t, we maintain a queue to record TB,i,t and update it by adding the next time slot t + 1 and removing the time slots that no longer influence time slot t + 1 to obtain  TB,i,t+1  . The update time (F )

(F )

cost of all users’ queues is O n · wmax , where wmax represents the maximum window size among all users’ forward windows. For each user’s historical publication budgets, we (B) (B) maintain another queue of size wmax , where wmax represents the maximum window size among all users’ backward windows. The time cost of calculating remaining backward   (B) budget upper bounds for all users is O n · wmax . Thus, (1)

(2)

the time complexity  of calculating  ϵt and ϵt for each (F ) (B) time slot is O wmax + wmax · n . The sample mechanism time complexity is O(n). Therefore, both DPBD   and  DPBA have a time complexity of O

(F )

(B)

wmax + wmax · n .

The remaining backward/forward budget computation is implemented here using a direct sliding-window summation for clarity. In practice, this step can be maintained incrementally via prefix sums or queue-based sliding-window data structures, reducing the amortized update cost from O(wmax ) to O(1) per user per time slot. Memory Complexity Analysis. For DPBD and DPBA, we have Theorem 7 as follows. Theorem 7 Both DPBD   and DPBA have complexity (F ) (B) O wmax + wmax · n . Proof For the process of OBS, the memory complexity is O(m). For each one of the n users in both DPBD and DPBA, (F ) (B) there are at most wmax forward window size data and wmax backward window size data  need to be stored.  Thus, the (F ) (B) memory complexity is O wmax + wmax · n . Scalability Discussion. DPBD and DPBA remain scalable for large user populations for the same reason as the fixed case (PBD and PBA), while incurring only additional bookkeeping for backward/forward privacy requirements. Thus, their per-time slot cost still depends on the current users and bounded window states rather than the full stream history. Privacy Analysis. The privacy analysis for DPBD and DPBA is presented in Theorem 8.

Theorem 8 DPBD and DPBA satisfy (t, wB , wF , E B , E F )-EPDP at each time slot t, where wB = (wB,1,t , . . . , wB,n,t ) and wF = (wF,1,t , . . . , wF,n,t ) represent the requirement sets for all users’ backward and forward window sizes at time stamp t, and E B = (EB,1,t , . . . , EB,n,t ) and E F = (EF,1,t , . . . , EF,n,t ) represent the requirement sets for all users’ backward and forward privacy budgets at time slot t. Proof Please refer to details of Theorem 8 in Appendix 8.4.2. Utility Analysis under Periodic Dynamic Requirements. To obtain a closed-form average error bound, we analyze a common recurrent setting in which each user’s privacy requirement sequence is periodic with period Y . That is for t > Y , each user’s privacy requirement at time slot t matches that at time slot t − Y . This periodicity assumption is introduced only for the utility analysis; the mechanisms DPBD and DPBA, as well as their privacy guarantees, do not require periodic privacy requirements. Such periodic requirements arise naturally in applications where user privacy preferences follow daily or weekly routines. For example, a commuter may request stronger privacy protection during regular commuting hours and weaker protection during working hours, leading to a daily repeated requirement pattern. Similarly, drivers or delivery workers may exhibit recurring work/rest schedules that induce periodic changes in privacy requirements. Besides, assume there are at most ŝ ≤ Y non-null publications occurring at time slots t1 , t2 ,. . . , tŝ . Assume each stream approximates the same number (ρsk ) of skipped publications and the same number (ρnu ) of nullified publica(F ) tions. Let EL (i) = mint EF,i,t be the minimal proposed forward privacy budget among all time slots for each ui . (B,M)

We define ϵL

(F )

(i) =

EL (i) (1) as the lower bound of ϵB,i,t 2βi

(2)

and ϵB,i,t , where βi is the parameter to be determined. (B,M)

We denote ϵBL = mini∈[n] ϵL (B,M) ϵR (i) =

(F ) EL (i) 2ηi

(i). Besides, we define (1)

(2)

as the upper bound of ϵB,i,t and ϵB,i,t , where ηi is the parameter to be determined. We also de(B,M) E note ϵBR = maxi∈[n] ϵR (i). Let ϵFL (i) = mint 2wF,i,t F,i,t be the half of minimal forward privacy budget share for ui among all time slots. Let ϵFLL = mini∈[n]ϵFL (i)
. Let ϵFLR = maxi∈[n]ϵFL (i) . Let γ
L = mini∈[n] 2ηi −1 − 1 and γR =
maxi∈[n] 2βi −1 − 1 . Let Z ′ = (n − nB ) n − nB + 14 be the sampling error upper bound, where nB is the quanE tity of maxi∈[n],t∈[T ] wF,i,t . For DPBD, we have Theorem 9 F,i,t as follows. Theorem 9 The average error per time slot in DPBD  is at most min d2 (min(ϵ 2 ,ϵ ))2 , Z ′ + d2 (max(ϵ 2 ,ϵ ))2 + FLL BL FLR BR  ŝ−γR +1  2(4ŝ−γL +1 +3γL −4) min 2(4 3ŝϵ2+3γR −4) , Z ′ + , 2 3ŝϵ BL

BR

Leilei Du1 et al.

18

where γL = mini∈[n] 2ηi −1 − 1 and γR =
maxi∈[n] 2βi −1 − 1 , if at most ŝ non-null publications occur in any period Y . Proof Please refer to details of Theorem 9 in Appendix 8.5.3. Interpretation of Theorem 9. The bound in Theorem 9 consists of the error from PartDC and the accumulated publication error from PartNOP over one period Y . The parameter ŝ denotes the maximum number of non-null publications in a period, while γL and γR characterize the transition range where the forward publication budget decreases from being above the backward-budget interval to below it. Hence, the bound decomposes the average error into several stages of the DPBD process, rather than treating it as a single opaque expression. Discussion on Consistency. When the dynamic forward and backward privacy requirements degenerate to fixed personalized privacy requirements, ϵFL (i) = (B,M ) (B,M ) ϵL (i) = ϵR (i) = Ei /(2wi ). Besides, γL = γR = 0, (min(ϵFLL , ϵBL ))2 = mini∈[n] (Ei /(2wi ))2 , (max(ϵFLR , ϵBR ))2 = maxi∈[n] (Ei /(2wi ))2 . For that matter, the error bound of DPBD reduces to the corresponding bound of the fixed personalized mechanism (PBD). This confirms that the dynamic analysis is consistent with the fixed-case analysis. Discussion on Tightness. The bound in Theorem 9 is tight up to constant factors in the following sense. When the number of non-null publications in each period is small, the PartDC term dominates, which matches the actual behavior of DPBD since most time slots reuse previous releases. When non-null publications occur close to the upper limit ŝ, the accumulated PartNOP terms dominate, again matching the mechanism behavior because more fresh releases consume more privacy budget and incur more noise. Therefore, the bound captures the correct dominant error source in both sparse-update and frequent-update regimes. For DPBA, we have Theorem 10 as follows. Theorem 10 The average error per time slot in DPBA is at most min d2 (min(ϵ 2 ,ϵ ))2 , Z ′ + d2 (max(ϵ 2 ,ϵ ))2 + (s,p) +ρnu errnlf ef rr PartNOP ρsk +ρnu +1

FLL BL

FLR BR

(s,p) f Part where the value of err is shown in NOP

Equation (4).

Proof Please refer to details of Theorem 10 in Appendix 8.5.4. Discussion on Frequent-Update Regimes. Similar to PBA, the error bound of DPBA becomes larger when skipped or nullified publications occur frequently. This effect concerns utility rather than privacy: the formal privacy guarantee of DPBA is still ensured by the budget-feasibility and composition analysis, whereas what may deteriorate in

frequent-update regimes is estimation accuracy. In practice, DPBA is therefore more suitable for smoother streams in which reuse of previous releases is effective, while DPBD is more appropriate for streams with persistent rapid changes. This interpretation is also consistent with our experimental observations that the absorption-based methods perform better on smoother synthetic streams, whereas the distributionbased methods are more competitive on rapidly changing real datasets. Designing an adaptive switching strategy between these two mechanism families is an interesting direction for future work.

6 Experiments 6.1 Datasets We evaluate our solutions on both real and synthetic datasets. Real datasets. We use two real-world datasets, Taxi [47, 48] and Foursquare [45, 44], to evaluate the performance of our algorithms. Taxi. It contains real-time trajectories of 10, 357 taxis’ in Beijing from February 2 to February 8, 2008. Each taxi has up to 154, 699 records, where each record comprises taxi id, data time, longitude and latitude. For the spatial dimension, we first remove all duplicate records, then extract records with longitude between 116 and 116.8 and latitude between 39.5 and [40.3], resulting in 14, 859, 377
records. We denote this area [116, 116.8] × [39.5, 40.3] as AE . Figure 10(a) shows 50% of uniformly extracted trajectory points in AE . We further divide AE uniformly into a 10 × 10 grids, designating these 100 cells as the location space. For the time dimension, we sample records every minute and get 8, 889 records. Foursquare. It contains 33, 278, 683 Foursquare checkins from 266, 909 users, during April 2012 to September 2013. Each record consists of user id, venue id (place), and time. We convert the venue id to the country where the venue is located. After removing invalid records, we uniformly extract 5% of users’ check-ins as shown in Figure 10(b). We set the publication time interval to 100 minutes, thus divide the chick-ins period into 7, 649 time slots. Synthetic datasets. We generate three binary stream datasets using different sequence models. Let pt = f (t) be the probability of setting the real value to 1 at time slot t. We set the length of each binary stream as T and the number of users as N . For each stream, we first generate a probability sequence (p1 , p2 , ..., pT ). At each time slot t, each user’s real value is set to 1 with probability pt and 0 otherwise. Among the three synthetic sequence models, only TLNS involves randomness due to the Gaussian perturbation term, while the Sin and Log sequences are deterministic once their

Personalized w-Event Privacy for Infinite Stream Estimation

19

!  2 2 2Hρ 2Hρ +1 +1   ′ sk sk  min , Z (ρ + 1) + if λLR ≥ λRL ;  sk  ϵ2 ϵ2   FLL FLR     2(ρ +1)   2 ′ 2 sk  if λLR < λRL and λL < ρsk + 1 ≤ λR ;  min ϵ2 Hρ +1 , Z (ρsk + 1) + ϵ2 sk (s,p) BR    FLL ef rrPart =   NOP  2λ 2 2 2   min Hλ , Z ′ λL + 2 L + (λR − λL ) min , n n + 14  L ϵ2 ϵ ϵ2   FLL BR  BL !      2 ρ −λR +1   2 sk  + min , (ρsk − λR + 1)Z ′ + 22 Hρ2 −λ +1 otherwise.  + ϵ2 R ϵ2 ϵ sk BR BL FLR

(4)

(a) Taxi

(b) Foursquare

Fig. 10: Illustration of Real datasets.

parameters are fixed. The probability functions we use are as follows: – TLNS function. In TLNS, pt = pt−1 + N (0, Q), where N (0, Q) is Gaussian noise with standard variance √ Q = 0.0025. We set p0 = 0.05 as the initial value. If pt < 0, we set pt = 0; If pt > 1, we set pt = 1. For reproducibility, the Gaussian perturbation in TLNS is generated using Java Random with a fixed seed of 1 in the revised implementation. Under the default setting with sequence length T = 10, 000, clipping occurs in 8 out of 10, 000 time slots (0.08%). All clipping events correspond to values falling below 0, while no values exceed 1. This indicates that clipping is very rare and has negligible impact on the temporal trend and statistical properties of the generated sequence. – Sin function. In Sin, pt = A sin (ωt) + h, where A = 0.05, ω = 0.01 and h = 0.075. – Log function. In Log, pt = A/(1 + e−bt ), where A = 0.25 and b = 0.01. 6.2 Experiment Setup We divide the total time series into two batches for all datasets, with each batch containing at most half of the total time slots. We compare our PBD, PBA, DPBD and DPBA with three non-personalized methods: Budget Distribution (BD), Budget Absorption (BA) [25] and SPAS [29]. We also compare against a simple personalized LDP method, Personalized LDP Budget Uniform (PLBU), which extends LDP Budget Uniform (LBU) [34] by replacing the inner CDP mechanism with an LDP mechanism. Let E and w be the privacy budget and window size in non-personalized static methods (BD, BA and SPAS). For non-personalized static methods, we set the E to vary from 0.2 to 1.0 and w to vary from 40 to 200. To make our PBD

Table 4: Experimental settings. Parameters Values static privacy budget E 0.2, 0.4, 0.6, 0.8, 1.0 static window size w 40, 80, 120, 160, 200 personalized privacy budget Ei E, . . . , 0.8, 1.0 40, 80, . . . , w personalized window size wi users’ quantity ratio o 0.1, 0.3, 0.5, 0.7, 0.9 forward privacy budget EF,i,t Ei , . . . , 0.8, 1.0 forward window size wF,i,t 40, 80, . . . , wi backward privacy budget EB,i,t 10 1 backward window size wB,i,t

and PBA comparable with the non-personalized static methods, we set the lower bound of each user’s privacy budget as E and the upper bound of each user’s window size as w in PBD and PBA to match the requirement of privacy level. Similarly, to make DPBD and DPBA comparable with PBD and PBA, we set the lower bound of each user’s forward privacy budget as Ei and the upper bound of each user’s forward window size as wi . According to the design of DPBD and DPBA, the backward privacy requirement (backward privacy budget and window size) is independent of the forward privacy requirement. To study how the forward privacy requirement affects accuracy, we set the backward privacy level to a value that does not impact   the publi(2) (2) (2) cation budget decision, namely, ϵF,i,t = min ϵF,i,t , ϵB,i,t in DPBD and ϵFA,i,t = min(ϵFA,i,t , ϵUB,i,t ) in DPBA. Therefore, we set the backward privacy budget sufficiently large (i.e., EB,i,t = 10) and the backward window size sufficiently small (i.e., wB,i,t = 1). Given ñ different privacy budgets ϵ̃ = {ϵ1 , ..., ϵñ }, let N Pñ (ϵi ) be the count of budget value ϵi , and N (ϵ̃) = i=1 N (ϵi ) be the total count of all the budgets. For any (ϵi ) ϵi ∈ ϵ̃, we define the privacy budget ratio of ϵi as N N (ϵ̃) . Similarly, we define the window size ratio of any wi in dif(wi ) ferent window sizes w̃ = {w1 , ..., wñ } as N N (w̃) . We set the privacy domain as {0.5, 1.0} and the window size domain as {10, 20}. We alter the ratio o of Ei = 0.5 and wi = 10 from 0.1 to 0.9. The parameters are shown in Table 4, where the default values are in bold font. We run the experiments on an Intel(R) Xeon(R) Silver 4210R CPU @ 2.4GHz with 128 RAM in Java. Each experiment is run 10 times, and we report the average result.

Leilei Du1 et al.

20

6.3 Measures We evaluate the performance of different mechanisms based on their data utility. We measure data utility as Average Mean Relative Error (AMRE) and Average Jensen-Shannon Divergence (AJSD, D̄JS ). Let T represent the number of time slots and d denote the dimension of data. AMRE is defined as the average value of Mean Relative Error (MRE), which is AMRE =

T T 1 X 1 1 X MREτ = ∥r τ − cτ ∥22 . T τ =1 T τ =1 d

(5)

Besides, AJSD is defined as the average value of JensenShannon Divergence (JSD, DJS ) [30], which is based on Kullback-Leibler Divergence [27], as D̄JS (r∥c) T

=

1 X D (r∥c) T τ =1 JS

=

1 X T τ =1

=

1 XX 2T τ =1 j=1

T

T



1 1 D (r∥v) + DKL (c∥v) 2 KL 2 d



 r τ (j) log

r τ (j) v τ (j)

(6)





 + cτ (j) log

cτ (j) v τ (j)

 ,

where v represents the average distribution of r and c, i.e., v(j) = 12 (r(j) + c(j)). For time slot τ , rτ (j) and cτ (j) represent the j-th dimensional values in the obfuscated and original data, respectively. In this subsection, we compare the performance of BD, BA, PLBU, PBD and PBA using AJSD metric. 6.4 Overall Utility Analysis Table 5 shows the average mean relative error AMRE as the privacy budget E varies. Across most datasets, AMRE generally decreases as E increases, since a larger E reduces the variance of the injected noise. However, the sensitivity of AMRE to E differs across mechanisms and datasets. On real datasets, distribution-based methods such as PBD and DPBD show a more evident reduction as E increases, whereas on synthetic datasets, absorption-based methods such as PBA and DPBA are more sensitive to the privacy budget and achieve larger reductions. This difference is mainly caused by the temporal characteristics of the streams: real datasets contain more abrupt changes and thus benefit from more responsive budget distribution, while synthetic datasets evolve more smoothly and benefit more from absorbing budgets for fewer but more accurate releases. We attribute this difference mainly to the temporal characteristics of the data streams. The real datasets exhibit stronger temporal variability and more abrupt changes across consecutive time slots, whereas the synthetic datasets are relatively smoother over time. When the stream changes rapidly, the dissimilarity between the current statistics and

the previous release becomes large, thus, mechanisms that allocate budget more responsively to the current time slot are more effective. In this case, PBD publishes more new statistical results than PBA, because PBD always reserves part of its privacy budget for the next time slot. Therefore, PBD achieves lower AMRE than PBA on the real datasets. In contrast, when the stream evolves more smoothly, the dissimilarity between consecutive time slots remains relatively small, when the density function changes gradually, the dissimilarity at each time slot remains small. In such cases, concentrating budget on fewer but more accurate releases is more beneficial than publishing more frequently. Therefore, PBA performs significantly better than PBD on the synthetic datasets. DPBD performs better than PBD, while DPBA performs better than PBA. This improved performance occurs because the dynamic personalized methods maintains a higher privacy budget of at least Ei and a small window size of at most wi compared to the personalized methods. Both a large privacy budget and a small window size contribute to improved accuracy. PLBU performs worse than other methods across all datasets except for TLNS, since LDP methods achieve lower accuracy than CDP methods under the same privacy budget. The comparison with SPAS further confirms this observation. On the two real datasets, Taxi and Foursquare, SPAS generally yields much larger AMRE than the proposed personalized mechanisms. Although SPAS adaptively allocates privacy budgets under homogeneous w-event privacy, it still relies on a single global privacy requirement and cannot exploit heterogeneous user-specific budgets and window sizes. This limitation becomes more evident on real streams with abrupt temporal changes, where more responsive personalized budget distribution is needed. In contrast, on the synthetic datasets, SPAS is more competitive with some distribution-based methods, especially when the stream evolves smoothly. Nevertheless, the absorptionbased methods, particularly PBA and DPBA, still achieve smaller AMRE in most cases because they can skip or nullify unnecessary publications, accumulate more budget for informative releases, and use OBS to reduce the reporting error. For the real datasets, our PBD consistently outperforms non-personalized methods. The AMRE of PBD is on average 72.6% lower than that of BD on Taxi dataset and 72.0% lower on Foursquare dataset. Besides, the AMRE of DPBD is on average 73.5% lower than that of BD on Taxi dataset and 93.3% lower on Foursquare dataset. We note that this performance gap is not primarily explained by dimensionality alone; the additional dimensionality analysis in Fig 17 in Appendix 8.3 shows that PBD/DPBD remain better than PBA/DPBA across different dimensions on the real datasets.

Personalized w-Event Privacy for Infinite Stream Estimation

21

Table 5: Average Mean Relative Error (AMRE) with E varied.

Datasets

Taxi

Foursquare

TLNS

Sin

Log

Methods BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA

E=0.2 8,459.58 3,050.51 34,419.70 618,995.29 1,203.40 2,874.89 613.25 795.28 13,725.14 7,162.41 180,722.61 603,754.52 2,185.22 7,491.81 460.58 1,675.06 35,214,891.91 72,479.55 9,750,998.15 3,276,401.46 5,625,685.13 15,734.77 4,108,894.40 3,249.53 14,809,297.94 61,604.76 18,127,404.96 234,146.85 1,065,153.09 26,390.31 376,035.19 8,258.50 12,598,827.10 25,313.21 6,334,895.72 23,030.09 580,200.16 9,856.66 75,571.46 1,788.03

E=0.4 2,156.19 1,495.79 34,415.11 154,449.26 449.91 1,369.62 327.08 534.17 3,544.35 3,411.68 180,706.57 149,939.73 725.76 3,681.56 167.42 1,020.44 26,932,213.28 13,456.32 9,732,708.88 2,774,019.75 5,708,081.90 7,593.93 4,001,623.91 2,096.95 3,868,423.13 21,010.09 18,103,836.01 208,385.79 891,132.17 12,807.53 331,161.83 4,668.58 3,106,749.11 7,067.12 6,323,757.64 21,985.85 438,397.59 4,316.13 59,450.90 1,415.64

For synthetic datasets, our PBA consistently outperforms other non-personalized methods and our DPBA further improves upon PBA. Compared to BA, the AMRE of PBA is lower on average of 30.2% on TLNS , 24.6% on Sin, and 21.1% on Log. Besides, the AMRE of DPBA is lower on average by 70.6% on TLNS, 61.0% on Sin, and 63.6% on Log. Moreover, our PBD consistently outperforms BD. Table 6 shows the average mean relative error AMRE as the window size w varies. As w increases, AMRE generally increases. This occurs because a large window size results in a small privacy budget at each time slot, leading to increased error. PLBU shows lower performance than other methods on most datasets, since LDP methods achieve lower accuracy than CDP methods under equivalent privacy budgets. SPAS is sensitive to the window size. Although it achieves very small AMRE on the real datasets when w = 40,

E=0.6 990.69 961.62 34,417.54 68,648.03 275.14 1,041.83 255.70 461.53 1,704.59 2,225.49 180,700.83 67,711.28 482.02 2,672.96 114.14 749.20 21,900,899.91 5,228.94 9,719,230.14 2,506,067.88 5,761,339.31 4,031.24 4,254,805.65 1,309.70 2,822,001.85 9,193.50 18,082,416.37 190,648.17 796,008.09 7,805.06 321,423.27 3,350.10 1,520,101.37 3,701.09 6,316,533.20 21,573.75 438,337.35 3,365.33 50,179.75 1,405.98

E=0.8 610.25 679.88 34,416.61 38,946.65 204.53 869.90 223.15 419.98 938.09 1,332.70 180,694.79 37,846.80 347.09 1,990.94 82.10 551.41 19,202,732.21 2,583.01 9,705,975.87 2,359,560.64 5,761,668.46 2,415.89 4,059,568.08 1,097.65 2,166,052.12 4,678.60 18,052,150.71 185,012.37 753,028.43 4,123.15 315,928.35 2,269.24 1,159,412.40 2,351.14 6,306,368.84 21,520.27 362,035.74 2,339.70 51,748.11 1,174.66

E=1 409.43 558.63 34,416.79 25,004.66 166.84 723.00 195.87 396.67 664.04 1,159.01 180,687.04 24,564.06 253.75 1,377.30 66.04 407.95 19,317,360.81 1,447.21 9,688,944.63 2,246,597.48 6,168,585.37 1,449.54 4,156,445.29 860.35 2,875,381.82 2,659.74 18,028,552.72 179,534.63 689,846.46 2,661.26 312,774.69 1,974.88 912,889.07 1,763.29 6,298,869.11 20,983.06 320,952.59 1,837.17 46,332.37 1,178.10

its error increases sharply when the window size becomes larger. This suggests that the homogeneous adaptive strategy of SPAS becomes less robust when the privacy budget must be allocated over longer windows. In comparison, the proposed personalized mechanisms show more stable performance across different window sizes. On real datasets, PBD and DPBD achieve lower AMRE than the corresponding non-personalized baselines, while on synthetic datasets, PBA and DPBA remain more effective due to their budget absorption strategy. For real datasets, our DPBD achieves the lowest error compared to others methods. The AMRE of PBD is on average 63.3% lower than that of BD on Taxi dataset and 65.8% on Foursquare dataset. Besides, the AMRE of DPBD is on average 62.7% lower than that of BD on Taxi dataset and 85.8% on Foursquare dataset. For synthetic datasets,

Leilei Du1 et al.

22 Table 6: Average Mean Relative Error (AMRE) with w varied.

Datasets

Taxi

Foursquare

TLNS

Sin

Log

Methods BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA BD BA PLBU SPAS PBD PBA PDBD PDBA

w=40 163.02 294.60 34,410.72 29.37 100.42 303.99 157.04 98.77 241.39 255.27 180,654.54 36.42 120.07 981.55 102.81 109.47 10,321,505.61 387.96 9,629,126.83 4,002,347.34 4,177,406.45 381.45 3,579,033.68 225.51 769,929.84 611.27 17,907,365.61 226,588.50 378,448.77 649.14 260,132.70 445.32 110,158.58 770.17 6,256,580.11 32,948.08 47,909.95 820.44 31,028.42 633.30

w=80 447.18 608.41 34,415.09 39,224.91 206.72 747.23 177.12 333.17 687.78 1,240.90 180,701.20 37,353.95 297.72 1,988.55 105.90 388.57 16,427,785.34 1,948.21 9,695,808.71 1,766,335.27 4,841,586.74 1,835.74 3,799,459.12 846.94 1,285,735.11 3,322.22 18,032,304.84 170,583.07 572,317.51 3,298.99 300,682.17 1,764.71 750,581.32 2,006.90 6,298,876.91 22,013.63 207,973.60 1,946.36 47,844.35 1,162.11

our DPBA demonstrates the lowest error among all nondynamic methods. Compared to BA, the AMRE of PBA is lower by an average of 22.9% for TLNS, 11.4% for Sin, and 11.7% for Log, respectively. DPBA further reduces the AMRE by an average of 66.6% for TLNS, 54.6% for Sin, and 53.6% for Log, respectively. Moreover, our PBD consistently outperforms BD across all datasets. In summary, our PBD and DPBD demonstrate superior performance on real datasets, with an AMRE at least 63.3% and 62.7% lower than BD, respectively. For synthetic datasets, our PBA and DPBA outperform BA with at least 11.4% and 53.6% smaller AMRE, respectively. For the experimental results under the AJSD metric, please refer to Section 8.2 for details.

w=120 990.69 961.62 34,417.54 68,648.03 275.14 1,041.83 255.70 461.53 1,704.59 2,225.49 180,700.83 67,711.28 482.02 2,672.96 114.14 749.20 21,900,899.91 5,228.94 9,719,230.14 2,506,067.88 5,761,339.31 4,031.24 4,254,805.65 1,309.70 2,822,001.85 9,193.50 18,082,416.37 190,648.17 796,008.09 7,805.06 321,423.27 3,350.10 1,520,101.37 3,701.09 6,316,533.20 21,573.75 438,337.35 3,365.33 50,179.75 1,405.98

w=160 1,853.31 1,333.79 34,415.33 84,345.03 477.71 1,549.01 275.78 642.48 2,910.86 3,112.29 180,713.97 81,441.64 819.29 3,715.36 112.99 1,245.98 22,192,516.74 9,421.72 9,732,079.75 3,060,865.41 5,943,316.00 6,285.94 4,320,520.18 2,073.61 3,444,317.33 16,455.49 18,107,904.18 207,628.80 1,144,032.83 13,784.27 345,762.45 5,505.09 3,170,285.91 5,943.62 6,325,047.93 24,442.50 582,733.67 4,270.21 60,542.04 1,617.49

w=200 3,060.57 1,664.90 34,416.53 69,863.51 673.23 1,879.14 297.00 784.93 4,783.33 3,758.29 180,722.91 68,097.75 1,022.65 4,636.11 128.03 1,634.49 22,368,956.59 16,065.42 9,741,718.28 3,527,531.79 6,268,467.82 7,870.36 4,344,081.28 2,985.93 6,933,306.34 25,231.48 18,118,392.15 217,991.62 1,339,405.34 17,342.63 365,804.39 7,833.50 8,658,570.30 7,973.24 6,327,726.59 22,909.65 759,567.65 6,007.43 66,902.55 2,122.58

6.5 Impact of User Requirement Type We define a set of users with privacy requirement as (wk , Ek )-requirement type. In this subsection, we examine the impact of user type on the utility. For our analysis, we set Ek candidate set as {0.6, 1.0} with a default value of 0.6, and the wk candidate set as {40, 120} with a default value of 120. We first vary the users’ quantity ratio of Ek = 1.0 from 0.1 to 0.9 while keeping wk = 120, and then vary the users’ quantity ratio of wk = 40 from 0.1 to 0.9 while keeping Ek = 0.6. We analyze the impact of these ratio variations on AMRE. Figure 11 illustrates the change in users’ quantity ratio for Ek = 1.0 from 0.1 to 0.9, with a fixed window size of wk = 120. Figure 12 shows the effect on changing users’ quantity for wk = 40 from 0.1 to 0.9, with a fixed privacy

Personalized w-Event Privacy for Infinite Stream Estimation

23

15 10

0.1 0.3 0.5 0.7 0.9 o of ²k =1.0

(a) Taxi

PBD

PBA

15 10

0.1 0.3 0.5 0.7 0.9 o of ²k =1.0

(b) Foursquare

ln(AMRE)

7

BA

ln(AMRE)

6 0.1 0.3 0.5 0.7 0.9 o of ²k =1.0

8

ln(AMRE)

7

ln(AMRE)

ln(AMRE)

BD

15 10

0.1 0.3 0.5 0.7 0.9 o of ²k =1.0

(c) TLNS

0.1 0.3 0.5 0.7 0.9 o of ²k =1.0

(d) Sin

(e) Log

Fig. 11: Average Mean Relative Error (AMRE) with ratio for privacy budget varied.

0.1 0.3 0.5 0.7 0.9 o of wk =40

0.1 0.3 0.5 0.7 0.9 o of wk =40

(a) Taxi

(b) Foursquare

PBD

15

PBA

10 0.1 0.3 0.5 0.7 0.9 o of wk =40 (c) TLNS

15

15

ln(AMRE)

7

BA

ln(AMRE)

6

8

ln(AMRE)

7

ln(AMRE)

ln(AMRE)

BD

10 0.1 0.3 0.5 0.7 0.9 o of wk =40 (d) Sin

10 0.1 0.3 0.5 0.7 0.9 o of wk =40 (e) Log

Fig. 12: Average Mean Relative Error (AMRE) with ratio for window size varied.

budget of Ek = 0.6. We observe that as the users’ quantity ratio increases, the AMRE remains relatively stable. However, when the users’ quantity ratio of Ek = 1.0 or wk = 40 exceeds 0.8, we can see a significant decrease in AMRE for PBD and PBA. This occurs because when the ratios surpasses a certain threshold, the optimal budget from OBS in Algorithm 1 becomes dominated by a higher E, resulting in lower error.

7 Conclusion In this paper, we address the problem of Personalized wEvent Private Publishing for Infinite Data Streams. We propose a mechanism called PWSM and two methods called PBD and PBA to solve this problem in scenarios with personalized privacy budget and window sizes for each users. Besides, we propose two dynamic solutions called DPBD and DPBA to solve this problem in scenarios with dynamic personalized privacy budget and window sizes. We also compare our PBD, PBA, DPBD and DPBA with recent solutions to demonstrate their efficiency and effectiveness. Our future work will focus on developing local differential privacy mechanisms that adapt to users’ evolving privacy preferences in local settings while preserving data utility. Besides, we plan to optimize our algorithms for highspeed data streams and expand their application to realworld scenarios like mobile crowd sensing and social media analysis.

References 1. A LAGGAN , M., G AMBS , S., AND K ERMARREC , A. Heterogeneous differential privacy. J. Priv. Confidentiality 7, 2 (2016).

2. A NDR ÉS , M. E., B ORDENABE , N. E., C HATZIKOKOLAKIS , K., AND PALAMIDESSI , C. Geo-indistinguishability: differential privacy for location-based systems. In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013 (2013), A. Sadeghi, V. D. Gligor, and M. Yung, Eds., ACM, pp. 901–914. 3. BAO , E., YANG , Y., X IAO , X., AND D ING , B. CGM: an enhanced mechanism for streaming data collection with local differential privacy. Proc. VLDB Endow. 14, 11 (2021), 2258–2270. 4. BASSILY, R., AND S MITH , A. D. Local, private, efficient protocols for succinct histograms. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 (2015), R. A. Servedio and R. Rubinfeld, Eds., ACM, pp. 127–135. 5. B LUM , A., L IGETT, K., AND ROTH , A. A learning theory approach to non-interactive database privacy. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008 (2008), pp. 609–618. 6. B OLOT, J., FAWAZ , N., M UTHUKRISHNAN , S., N IKOLOV, A., AND TAFT, N. Private decayed predicate sums on streams. In Joint 2013 EDBT/ICDT Conferences, ICDT ’13 Proceedings, Genoa, Italy, March 18-22, 2013 (2013), pp. 284–295. 7. C HAN , T. H., S HI , E., AND S ONG , D. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur. 14, 3 (2011), 26:1–26:24. 8. C HEN , Y., M ACHANAVAJJHALA , A., H AY, M., AND M IKLAU , G. Pegasus: Data-adaptive differentially private stream processing. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017 (2017), pp. 1375–1388. 9. C HEU , A. Differential privacy in the shuffle model: A survey of separations. CoRR abs/2107.11839 (2021). 10. C HEU , A., S MITH , A. D., U LLMAN , J. R., Z EBER , D., AND Z HILYAEV, M. Distributed differential privacy via shuffling. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I (2019), Y. Ishai and V. Rijmen, Eds., vol. 11476 of Lecture Notes in Computer Science, Springer, pp. 375–403.

24 11. C UMMINGS , R., F ELDMAN , V., M C M ILLAN , A., AND TAL WAR , K. Mean estimation with user-level privacy under data heterogeneity. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022 (2022). 12. D ONG , W., L UO , Q., AND Y I , K. Continual observation under user-level differential privacy. In 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, May 21-25, 2023 (2023), pp. 2190–2207. 13. D U , L., C HENG , P., C HEN , L., S HEN , H. T., L IN , X., AND X I , W. Infinite stream estimation under personalized w-event privacy. Proc. VLDB Endow. 18, 6 (2025), 1111–1123. 14. D U , L., C HENG , P., Z HENG , L., X I , W., L IN , X., Z HANG , W., AND FANG , J. Dynamic private task assignment under differential privacy. In 39th IEEE International Conference on Data Engineering, ICDE 2023, Anaheim, CA, USA, April 3-7, 2023 (2023), pp. 2740–2752. 15. DVIJOTHAM , K. D., M C M AHAN , H. B., P ILLUTLA , K., S TEINKE , T., AND T HAKURTA , A. Efficient and near-optimal noise generation for streaming differential privacy. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 (2024), pp. 2306– 2317. 16. DWORK , C. Differential privacy. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II (2006), M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, Eds., vol. 4052 of Lecture Notes in Computer Science, Springer, pp. 1– 12. 17. DWORK , C. Differential privacy in new settings. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010 (2010), pp. 174–183. 18. DWORK , C., NAOR , M., P ITASSI , T., AND ROTHBLUM , G. N. Differential privacy under continual observation. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 (2010), pp. 715–724. 19. DWORK , C., AND ROTH , A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9, 3-4 (2014), 211–407. 20. E RLINGSSON , Ú., P IHUR , V., AND KOROLOVA , A. RAPPOR: randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-7, 2014 (2014), G. Ahn, M. Yung, and N. Li, Eds., ACM, pp. 1054–1067. 21. FAN , L., AND X IONG , L. An adaptive approach to real-time aggregate monitoring with differential privacy. IEEE Trans. Knowl. Data Eng. 26, 9 (2014), 2094–2106. 22. F ENG , S., M OHAMMADY, M., WANG , H., L I , X., Q IN , Z., AND H ONG , Y. DPI: ensuring strict differential privacy for infinite data streaming. In IEEE Symposium on Security and Privacy, SP 2024, San Francisco, CA, USA, May 19-23, 2024 (2024), pp. 1009– 1027. 23. G UO , P., J IANG , T., Z HANG , Q., AND Z HANG , K. Sleep scheduling for critical event monitoring in wireless sensor networks. IEEE Trans. Parallel Distributed Syst. 23, 2 (2012), 345– 352. 24. J ORGENSEN , Z., Y U , T., AND C ORMODE , G. Conservative or liberal? personalized differential privacy. In 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015 (2015), pp. 1023–1034.

Leilei Du1 et al. 25. K ELLARIS , G., PAPADOPOULOS , S., X IAO , X., AND PAPADIAS , D. Differentially private event sequences over infinite streams. Proc. VLDB Endow. 7, 12 (2014), 1155–1166. 26. KOTSOGIANNIS , I., D OUDALIS , S., H ANEY, S., M ACHANAVA JJHALA , A., AND M EHROTRA , S. One-sided differential privacy. In 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020 (2020), pp. 493–504. 27. K ULLBACK , S., AND L EIBLER , R. A. On information and sufficiency. The annals of mathematical statistics 22, 1 (1951), 79–86. 28. L I , X., C AO , Y., AND YOSHIKAWA , M. Locally private streaming data release with shuffling and subsampling. In 39th IEEE International Conference on Data Engineering, ICDE 2023 - Workshops, Anaheim, CA, USA, April 3-7, 2023 (2023), IEEE, pp. 125– 131. 29. L I , X., L I , T., C HENG , Y., G ONG , C., R EN , K., Q IN , Z., AND WANG , T. SPAS: continuous release of data streams under wevent differential privacy. Proc. ACM Manag. Data 3, 1 (2025), 78a:1–78a:27. 30. L IN , J. Divergence measures based on the shannon entropy. IEEE Trans. Inf. Theory 37, 1 (1991), 145–151. 31. L IU , J., L OU , J., X IONG , L., L IU , J., AND M ENG , X. Projected federated averaging with heterogeneous differential privacy. Proc. VLDB Endow. 15, 4 (2021), 828–840. 32. M OON , W., H YUN , S., PARK , S., PARK , D., AND H EO , J. Query - dependent video representation for moment retrieval and highlight detection. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023 (2023), pp. 23023–23033. 33. M URAKAMI , T., AND K AWAMOTO , Y. Utility-optimized local differential privacy mechanisms for distribution estimation. In 28th USENIX Security Symposium, USENIX Security 2019, Santa Clara, CA, USA, August 14-16, 2019 (2019), pp. 1877–1894. 34. R EN , X., S HI , L., Y U , W., YANG , S., Z HAO , C., AND X U , Z. LDP-IDS: local differential privacy for infinite data streams. In SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 (2022), pp. 1064–1077. 35. S UN , D., D ONG , W., Q IU , Y., AND Y I , K. Personalized truncation for personalized privacy. Proc. ACM Manag. Data 2, 6 (2024), 249:1–249:25. SIGMOD 2025. 36. T ENENBAUM , J., K APLAN , H., M ANSOUR , Y., AND S TEMMER , U. Concurrent shuffle differential privacy under continual observation. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA (2023), A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, Eds., vol. 202 of Proceedings of Machine Learning Research, PMLR, pp. 33961–33982. 37. WANG , Q., Z HANG , Y., L U , X., WANG , Z., Q IN , Z., AND R EN , K. Rescuedp: Real-time spatio-temporal crowd-sourced data publishing with differential privacy. In 35th Annual IEEE International Conference on Computer Communications, INFOCOM 2016, San Francisco, CA, USA, April 10-14, 2016 (2016), pp. 1– 9. 38. WANG , S., L I , J., P ENG , Y., C HEN , K., YANG , W., J IANG , H., AND L I , J. Differential private data stream analytics in the local and shuffle models. IEEE Trans. Mob. Comput. 24, 7 (2025), 6701–6717. 39. WANG , T., C HEN , J. Q., Z HANG , Z., S U , D., C HENG , Y., L I , Z., L I , N., AND J HA , S. Continuous release of data streams under both centralized and local differential privacy. In CCS ’21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15 - 19, 2021 (2021), pp. 1237–1253.

Personalized w-Event Privacy for Infinite Stream Estimation 40. WANG , Z., H U , J., LV, R., W EI , J., WANG , Q., YANG , D., AND Q I , H. Personalized privacy-preserving task allocation for mobile crowdsensing. IEEE Trans. Mob. Comput. 18, 6 (2019), 1330– 1341. 41. WANG , Z., L IU , W., PANG , X., R EN , J., L IU , Z., AND C HEN , Y. Towards pattern-aware privacy-preserving real-time data collection. In 39th IEEE Conference on Computer Communications, INFOCOM 2020, Toronto, ON, Canada, July 6-9, 2020 (2020), pp. 109–118. 42. X IE , Y., PAN , Z., M A , J., J IE , L., AND M EI , Q. A prompt log analysis of text-to-image generation systems. In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023 (2023), pp. 3892–3902. 43. X UE , Q., Y E , Q., H U , H., Z HU , Y., AND WANG , J. DDRM: A continual frequency estimation mechanism with local differential privacy. IEEE Trans. Knowl. Data Eng. 35, 7 (2023), 6784–6797. 44. YANG , D., Z HANG , D., C HEN , L., AND Q U , B. Nationtelescope: Monitoring and visualizing large-scale collective behavior in lbsns. J. Netw. Comput. Appl. 55 (2015), 170–180. 45. YANG , D., Z HANG , D., AND Q U , B. Participatory cultural mapping based on collective behavior data in location-based social networks. ACM Trans. Intell. Syst. Technol. 7, 3 (2016), 30:1–30:23. 46. Y E , Q., H U , H., H UANG , K., AU , M. H., AND X UE , Q. Stateful switch: Optimized time series release with local differential privacy. In IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, New York City, NY, USA, May 17-20, 2023 (2023), pp. 1–10. 47. Y UAN , J., Z HENG , Y., X IE , X., AND S UN , G. Driving with knowledge from the physical world. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011 (2011), pp. 316–324. 48. Y UAN , J., Z HENG , Y., Z HANG , C., X IE , W., X IE , X., S UN , G., AND H UANG , Y. T-drive: driving directions based on taxi trajectories. In 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2010, November 3-5, 2010, San Jose, CA, USA, Proceedings (2010), pp. 99–108.

8 Appendix 8.1 Running time Analysis In this subsection, we compare the running time of BD, BA, PBD, PBA, DPBD and DPBA. Figure 13 shows the average running time per time slot as the privacy budget varies from 0.2 to 1. The running time remains statble across different privacy budgets. This stability occurs because the privacy level does not impact on the running time. DPBD requires the highest computation time among all methods, while BD requires the least time. What’s more, each of the personalized budget distribution methods (PBD, and DPBD) runs slower than its relative personalized budget absorption methods (PBA and DPBA). It is because personalized budget absorption methods are more likely to skip a publication than personalized budget distribution methods, which leads to fewer non-null publication calculations. Figure 14 shows the average running time per time slot as the window size changes from 40 to 200. The running time decreases as the window size increases. This occurs because large window sizes result in more skipped time slots or nullified time slots, reducing the overall calculation time. Similar to Figure 13, BD requires the least running time among all methods, while personalized budget distribution

25 methods (PBA and DPBA) require the more running time. It is because personalized methods introduce an optimal budget selection step that increases the running time. Compared to personalized budget absorption methods, the dissimilarity of personalized budget distribution methods increases more rapidly than the error, resulting in fewer skips or nullifications.

8.2 Experiments under AJSD Metric Figure 15 shows the results of AJSD as the privacy budget E varies from 0.2 to 1. For all methods, AJSD decreases as E increases, which is broadly consistent with the AMRE trend in Section 6.4. PLBU performs worse than CDP-based methods on most datasets, since LDP methods generally provide lower utility under the same privacy budget. Both PBD and PBA outperform BD across all datasets. DPBD achieves the lowest AJSD on the two real datasets, while DPBA performs best with the three synthetic datasets. Notably, the AJSD ranking is not always identical to the AMRE ranking. This is expected because AMRE measures pointwise estimation error, whereas AJSD evaluates similarity between the released and true distributions. Therefore, AJSD captures a different aspect of utility and should be viewed as a complementary distribution-level metric, rather than as direct evidence for the same causal explanation used for AMRE. Figure 16 shows the results of AJSD as the window size w varies from 20 to 200. AJSD generally increases with larger window sizes for all methods, since a larger window reduces the effective privacy budget available at each time slot. PLBU again shows lower utility than the CDP-based methods on most datasets. Consistent with Figure 15, both PBD and PBA outperform BD. DPBD achieves the lowest AJSD on the two real datasets, while DPBA leads on the three synthetic datasets. Similar to Figure 15, these results should be interpreted together with AMRE rather than in isolation. In particular, the discrepancy between AMRE and AJSD on Foursquare suggests that distribution-level similarity and pointwise estimation accuracy may favor different mechanisms. For this reason, we avoid attributing the AJSD behavior to a single factor such as dimensionality or sparsity. The comparison with SPAS further supports the above observations under the AJSD metric. On the real datasets, SPAS usually yields larger AJSD than the proposed methods, which indicates that the proposed personalized mechanisms preserve distribution-level similarity more effectively than this homogeneous w-event baseline. On the synthetic datasets, SPAS can outperform some distribution-based methods, especially when the stream changes smoothly. However, PBA and DPBA still achieve the best or near-best AJSD in most cases, showing the advantage of budget absorption for smooth streams. Since AMRE measures pointwise relative error whereas AJSD evaluates the similarity between the released and true distributions, the results under these two metrics provide complementary evidence that the proposed personalized mechanisms improve data utility over a recent homogeneous w-event baseline while supporting a more general privacy model.

8.3 Experiments for Dimension Change Figure 17 reports the utility under different dimensional settings. For AMRE, we observe that PBD/DPBD consistently outperform PBA/DPBA on the real datasets across all tested dimensions. This suggests that the performance gap is not primarily caused by dimensionality. Instead, the main reason is the temporal characteristics of the real data streams. Since real datasets usually exhibit more rapid and irregular changes across consecutive time slots, the absorption-based strategy in PBA/DPBA becomes less effective, because skipped or nullified updates are more difficult to approximate accurately using previous

Leilei Du1 et al.

26

0.2 0.4 0.6 0.8 1.0

10 0.2 0.4 0.6 0.8 1.0

E

DPBD

10 5 0

E

(a) Taxi

PBA

DPBA

0.2 0.4 0.6 0.8 1.0

10 5 0

E

(b) Foursquare

average time (s)

5

20

PBD

average time (s)

10

BA

average time (s)

15

average time (s)

average time (s)

BD

0.2 0.4 0.6 0.8 1.0

10 0

E

(c) TLNS

0.2 0.4 0.6 0.8 1.0 E

(d) Sin

(e) Log

Fig. 13: The average running time per time slot with E varied.

40 80 120 160 200

w

40 80 120 160 200

w

(a) Taxi

PBA

DPBD

20 10 0

DPBA

40 80 120 160 200

20 10 0

w

(b) Foursquare

average time (s)

10

30 20 10

PBD

average time (s)

20

BA

average time (s)

30

average time (s)

average time (s)

BD

40 80 120 160 200

20 10

w

(c) TLNS

0

40 80 120 160 200

w

(d) Sin

(e) Log

Fig. 14: The average running time per time slot with w varied.

7.5 5.0

0.2 0.4 0.6 0.8 1.0 E

(a) Taxi

SPAS

0.2 0.4 0.6 0.8 1.0 E

PBD

PBA

DPBD

5 0 0.2 0.4 0.6 0.8 1.0 E

(b) Foursquare

DPBA

5 0 0.2 0.4 0.6 0.8 1.0

ln(AJSD)

PLBU

ln(AJSD)

5.0

BA

ln(AJSD)

7.5

ln(AJSD)

ln(AJSD)

BD

0 0.2 0.4 0.6 0.8 1.0

E

(c) TLNS

5

E

(d) Sin

(e) Log

Fig. 15: Average Jensen-Shannon Divergencee (AJSD) with E varied. releases. In contrast, PBD/DPBD allocate privacy budgets in a more responsive manner, which leads to lower pointwise estimation error. For AJSD, the trends are not always identical to those observed for AMRE. This is expected because AMRE measures pointwise estimation accuracy, whereas AJSD evaluates similarity between the released and true distributions. Therefore, we treat AJSD as a complementary utility metric that captures a different aspect of data quality. In the revised manuscript, we avoid attributing the AJSD behavior to a single factor such as dimensionality or sparsity, since the current results do not provide sufficient evidence for such a causal conclusion.



Ei /2 −

(2) k=tL ϵi,k

Pt−1



/2. For any time slot t ∈ [1, wi ], the summa
P i k tion publication budgets used for ui is at most w ≤ k=1 Ei / 2 · 2 (Ei /2) · (1 − 1/2wi ) ≤ Ei /2. Pt (2) ≤ Ei /2 for t = wi + s i.e., Assume k=tL ϵi,k
Pwi +s (2) /2 . Then for t = wi + s + 1, we have: ϵ ≤ E i k=max(s+1,1) i,k wi +s+1

wi +s (2)

X

X

ϵi,k =

k=max(s+2,1)

(2)

(2)

ϵi,k + ϵi,wi +s+1 .

(8)

k=max(s+2,1)

(2)

Since ϵi,wi +s+1 is at most half of the remaining publication budget at time slot wi + s, thus,

8.4 Proof for Privacy Analysis

(2)

P i +s (2) Ei − w k=max(s+2,1) ϵi,k 2

(9)

8.4.1 Proof for Theorem 3

ϵi,wi +s+1 ≤

Proof We record max(t − wi + 1, 1) as tL for short. (1) PBD satisfies (w, E)-EPDP. In the process of PartDC , for each user ui , the dissimilarity budget at each time slot is Ei /(2wi ). Then for each time slot t, we have

Let k∗ = max(s+2, 1). According to Equations (8) and (9), we have:

t X k=tL

(1)

ϵi,k =

Ei . 2

(7)

In PartNOP , for each user ui at time slot t, only half of the pub(2) lication budget is used when non-null publication occurs: ϵi,t =

wi +s+1

X

2

wi +s (2)

ϵi,k ≤

X

(2)

ϵi,k +

P i +s (2) Ei − w k=k∗ ϵi,k 2

k=k∗

k=k∗

Pwi +s (2) k=k∗ ϵi,k

Ei + 4 Ei Ei + ≤ 4 4 Ei = . 2 =

2

.

2

Personalized w-Event Privacy for Infinite Stream Estimation

2.5

40

80 120 160 200

7.5 5.0 2.5

w

SPAS

40

(a) Taxi

80 120 160 200

w

PBD

PBA

5

DPBD

0 40

(b) Foursquare

DPBA

5

ln(AJSD)

PLBU

ln(AJSD)

5.0

BA

ln(AJSD)

7.5

ln(AJSD)

ln(AJSD)

BD

27

0

80 120 160 200

40

w

80 120 160 200

0 40 80 120 160 200

w

(c) TLNS

5

w

(d) Sin

(e) Log

Fig. 16: Average Jensen-Shannon Divergencee (AJSD) with w varied. BA

PBD

PBA

8 6 2

20

38

d

56

74

ln(AJSD)

ln(AMRE)

ln(AMRE)

10.0 7.5 5.0

(a) Taxi

2

DPBD

6

6 5 42

20 38 56 74

d

DPBA

ln(AJSD)

BD

20

(b) Foursquare

38

56

d

5 4

74

2

(c) Taxi

20

38

d

56

74

(d) Foursquare

Fig. 17: AMRE and AJSD with d varied. Therefore, for any t ≥ 1, we have: t X

(2)

ϵi,k ≤

k=tL

Ei . 2

(10)

According to the Composition Theorems [19] and Equation (7) and Equation (10), we have: t X

ϵi,k =

k=tL

t X

t X

(1)

ϵi,k +

k=tL

(2)

Fig. 18: An example for parameters in PBA.

ϵi,k ≤ Ei .

k=tL

Based on Algorithm 5, we have:

For any user ui and any two wi -neighboring stream prefixes St and St′ (i.e., St ∼wi St′ ), let ts be the earliest time slot where St [ts ] ̸= St′ [ts ] and te be the latest time slot where St [te ] ̸= St′ [te ]. Then we have te − ts + 1 ≤ wi . Denoting the output of our PBD as PBD(St [t]) = ot ∈ O, for any O ⊆ O, we have:

wi ≥

si X

(1 + 2αi,kj ) − αi,k1 − αi,ksi .

j=1

Then, for the total publication budgets used in any window, we have Pr[PBD(St [k]) = ok ] Pr[PBD(St ) ∈ O] te ≤ Πk=t s Pr[PBD(St′ ) ∈ O] Pr[PBD(St′ [k]) = ok ] ≤e ≤e

t X

Pte

k=ts ϵi,k

k=tL Pte

k=max (te −wi +1,1)

ϵi,k

≤ eEi . Therefore, PBD satisfies (w, E)-EPDP where w= (w1 , w2 , . . . , wn ) and E = (E1 , E2 , . . . , En ). (2) PBA satisfies (w, E)-EPDP. The PartDC in PBA is identical to that that in PBD. Consequently, for each time slot t, we have: t X

(1)

ϵi,k = Ei /2.

(11)

(2)

si Ei X · (1 + αi,kj ) 2wi j=1 P i Ei · sj=1 (1 + αi,kj ) ≤ Psi 2 j=1 (1 + 2αi,kj ) − 2αi,k1 − 2αi,ksi P i Ei · sj=1 (1 + αi,kj ) = Ps Psi −1 i 2 j=1 (1 + αi,kj ) + 2 j=2 αi,kj

ϵi,k ≤

≤

(12)

Ei . 2

Based on Equations (11) and (12), and applying the Composition Theorems [19], we obtain:

k=tL

In PartNOP , for any user ui and any window of size wi , there are si publication time slots in the window. We denote these publication time slots as (k1 , k2 , . . . , ksi ). For any publication time slot kj j ∈
[si ] , the quantity of its absorbing unused budgets is denoted as αi,kj . Figure 18 illustrates an example where si = 3 and wi = 9.

t X k=tL

ϵi,k =

t X k=tL

(1)

ϵi,k +

t X

(2)

ϵi,k ≤ Ei .

k=tL

The subsequent proof process follows the same steps as in PBD. Ultimately, we demonstrate that PBA also satisfies (w, E)-EPDP.

Leilei Du1 et al.

28

(1)

8.4.2 Proof for Theorem 8

From Equations (15) and (16), we have ÊF,i,t = ÊF,i,t + (2)

Proof We analyze the privacy guarantees of DPBD and DPBA sepa(1) (2) rately. Let ÊB,i,t = ÊB,i,t + ÊB,i,t represent the backward budget (1)

(2)

(1)

(2)

usage from max(t−wB,i,t +1) to t for ui , where ÊB,i,t and ÊB,i,t are the budget usages in sub-mechanism PartDC and PartNOP respec(1) (2) tively. Let ÊF,i,t = ÊF,i,t + ÊF,i,t represent the forward budget usage from max(t − wB,i,t + 1) to t for ui , where ÊF,i,t and ÊF,i,t are the budget usages in sub-mechanism PartDC and PartNOP respectively. (1) DPBD satisfies (t, wB , wF , E B , E F )-EPDP at each time slot t ∈ [T ]. For the backward privacy budget usage of each ui at time slot t, we have t X

(1)

ÊB,i,t =

ÊF,i,t ≤ EF,i,t /2 + EF,i,t /2 = EF,i,t . For any user ui at any time slot t and any two stream prefixes St , St′ satisfying St and St′ are wB,i,t -neighboring i.e., St ∼B,t,w

St′ and St and St′ are wF,i,t -neighboring i.e., St ∼F,t,w St′ . ′ Let ts be the minimal time slot with St [ts ] ̸= St [ts ] and te be the maximal time slot with St [ts ] ̸= St′ [ts ]. Then we have t − ts + 1 ≤ wB,i,t and te − t + 1 ≤ wF,i,t . Let ϵi,t be the privacy budget usage of ui at time slot t. Let the output of our DPBD as DPBD(St [t]) = ot ∈ O. For any O ⊆ O we have te Y Pr[DPBD(St ) ∈ O] Pr[DPBD(St [k]) = ok ] ≤ ′ Pr[DPBD(St ) ∈ O] Pr[DPBD(St′ [k]) = ok ] k=t s

≤e

(1)

≤e

ϵi,k

k=max(t−wB,i,t +1,1) (1) ϵi,k

(1)

=

EB,i,t (1) − ϵB,i,t 2

EB,i,t . 2

Besides, it holds t X

(2)

ÊB,i,t =

(2)

ϵi,k

k=max(t−wB,i,t +1,1) t−1 X

(2)

= ϵi,t +

(2)

ϵi,k

(14)

k=max(t−wB,i,t +1,1) (2)

≤ ϵB,i,t + =

EB,i,t (2) − ϵB,i,t 2

EB,i,t . 2 (1)

(1)

t+wF,i,t −1 X

(1)

ϵi,k

t+wF,i,t −1

X

≤

X

=

EF,i,t . 2

k=t

(15)

EF,i,t 2wF,i,t

(2) 2ϵi,τ . Therefore, it holds

(2)

t+wF,i,t −1 X

(2)

ϵi,k

k=t

EF,i,t (2) − 2ϵi,t+w F,i,t 2 EF,i,t ≤ . 2 ≤

X

(2)

ϵi,k

k=t

EF,i,t (2) ≤ − ϵi,t+wF,i,t 2 EF,i,t ≤ . 2 (2)

Thus, ÊF,i,t = ÊF,i,t + ÊF,i,t ≤ EF,i,t . The subsequent steps follow the same proof process as shown in DPBD. Therefore, DPBA satisfies (t, wB , wF , E B , E F )-EPDP.

8.5 Proof for Utility Analysis

In sub-mechanism PartNOP , given two time slot t and τ with t ≤ (2) (2) τ , according to the calculation process of ϵi,τ , we have 0 ≤ ϵi,τ ≤   P P EF,i,t E (2) −1 (2) −1 (2) ϵF,i,τ ≤ 12 − τk=t ϵi,k , thus τk=t ϵi,k ≤ F,i,t − 2 2

ÊF,i,t =

t+wF,i,t −1 (2)

ÊF,i,t =

(1)

(1)

ϵF,i,k

k=t t+wF,i,t −1

P e ϵi,k ϵi,k + tk=t

Let wB = (wB,1,t , . . . , wB,n,t ), wF = (wF,1,t , . . . , wF,n,t ), E B = (EB,1,t , . . . , EB,n,t ) and E F = (EF,1,t , . . . , EF,n,t ). Then, DPBD satisfies (t, wB , wF , E B , E F )-EPDP. (2) DPBA satisfies (t, wB , wF , E B , E F )-EPDP at each time slot t ∈ [T ]. In DPBA, the backward privacy budget usage for each ui at time slot t matches that of DPBD, which means ÊB,i,t ≤ EB,i,t . Similarly, the forward privacy budget usage in PartDC at time slot t is iden(1) tical to DPBD, resulting in ÊF,i,t ≤ EF,i,t /2. Next, we consider the forward privacy budget usage of each ui at time slot t in PartNOP . For any two time slots t and τ where t ≤ (2) (2) τ , based on the calculation process of ϵi,τ , we have 0 ≤ ϵi,τ ≤ P P E (2) (2) −1 (2) −1 (2) ϵFA,i,τ ≤ ϵUF,i,τ ≤ F,i,t − τk=t ϵi,k . Thus, τk=t ϵi,k ≤ 2

(2)

k=t

≤

k=ts

EF,i,t (2) − ϵi,τ . Therefore, we have 2

From Equations (13) and (14), we have ÊB,i,t = ÊB,i,t + ÊB,i,t ≤ EB,i,t /2 + EB,i,t /2 = EB,i,t . For the forward privacy budget usage of each ui at time slot t, in sub-mechanism PartDC we have ÊF,i,t =

Pt

≤ eEB,i,t +EF,i,t

(13)

k=max(t−wB,i,t +1,1)

≤ ϵB,i,t +

k=ts ϵi,k

= eÊB,i,t +ÊF,i,t

t−1 X

(1) = ϵi,t +

P te

(16)

8.5.1 Proof for Theorem 4 Proof Given a privacy budget-quantity pair set P and a positive number β, we define β · P = {(β · ϵj , nj )|(ϵj , nj ) ∈ P }. For each user ui with fixed personalized privacy requirement (wi , Ei ), we calEi culate their average budget per window as w . We denote the set of i n o Ei all average budgets as ϵ = w |i ∈ [n] . We then construct the prii vacy budget-quantity pair set of each type of average budget
as PA = {(ϵj , nj )|ϵj ∈ ϵ}. Let Z = (n − nA ) n − nA + 41 be the samEi pling error upper bound, where nA is the quantity of maxi∈[n] w in i ϵ.

Personalized w-Event Privacy for Infinite Stream Estimation

29

When PartDC is not private, the error stems from PartNOP . In PartNOP , errors arise from both non-null and non publications. According to the PartNOP , an null publication error does not exceed the nonnull publication error at the most recent publication time slot. For the average error errNOP of all time slots within the window of size wL , based on the PBD process, we have:   1 X wL 1 PA · ef rrO k+1 wL s̃ 2 k∈[s̃]   1 X 2 2   < min   2 , Z +  2  ϵL ϵR s̃

errNOP =

k∈[s̃]

2k+1



1 < min  s̃

X 8 · 4k

k∈[s̃]

= min

ϵ2L

2k+1

, s̃ · Z +

(17)

X 8 · 4k



ϵ2R



k∈[s̃]

32 · (4s̃ − 1) 32 · (4s̃ − 1) ,Z + 3s̃ϵ2L 3s̃ϵ2R

!

budget lower bound set for all users at skipped publication time slots (spanning α time slot) be ϵ̂ = {ϵ1 , ϵ2 , . . . , ϵα }. Then, the error upper bound of each skipped publication is the error of publishing new data using ϵk (k ∈ [α]). For example in Figure 19, the error upper bound at t3 is the error of publishing a new obfuscated statistic result using 1 3 { 3E , E22 , 3E , E44 }. 8 16
Let Z = (n − nA ) n − nA + 14 be the sampling error upper Ei bound, where nA is the number of users with maximum value of w . i We now consider the following two cases: Case α ≤ wL . In this case, the publication budget lower bound (sk) (pb) doubles with each time slot increasing. Let errNOP (α) and errNOP be the total error upper bounds of the α skipped publications and the non(s,p) null publication in PartNOP , respectively. Let errNOP be the error of all skipped publications and the publication in PartNOP . According to Lemma 1, we have

. err

  X 2 2 (sk) (α) < min ,Z + 2 2 NOP (kϵL ) (kϵR ) k∈[α]

When PartDC is private, the error from PartDC can lead to two scenarios: (1) falsely skipping a publication or (2) falsely performing a non-null publication. Both cases are bounded by the error in PartDC . In PartDC , we execute the SM with OBS. The sensitivity of dis is 1/d. For the average error errDC of each time slot in window size wL , according to Lemma 1, we have   errDC < min 

= min

≤ min

and err

(s,p)

NOP

 2 d2 mini∈[n]



Ei 2wi

8 8 ,Z + 2 2 d2 ϵ2L d ϵR

2 , Z +

2 d2 maxi∈[n]



Ei 2wi

 2 

(sk) (pb) (α) + err NOP NOP (sk) = err (α + 1) NOP

< err

= min

(18)

! .

Based on Equations (18) and (17), we can get the average error upper bound as errDC + errNOP .

! 2 2 2 2 H , αZ + H , ϵ2L α ϵ2R α

(19)

! 2 2 2 2 Hα+1 , (α + 1)Z + 2 Hα+1 . 2 ϵL ϵR

Thus, we derive the average error upper bound errNOP of each time slot in PartNOP as   1 (s,p) errNOP < ef rrNOP + α · errnlf , (20) 2α + 1 (s,p)

8.5.2 Proof for Theorem 5

where ef rrNOP is the final value in Equation (19). Case α > wL . In this case, we have err

Proof Similar to PBD, we first analyze the error of PartNOP in PBA by assuming PartDC is not private. We then add the error of PartDC , which is identical to that in PBD, to obtain the final total error. When PartDC is not private, the error stems from PartNOP . In PartNOP , each non-null publication corresponds to α skipped publications preceding it and α nullified publications succeeding it. For each ui ’s skipped publication, the publication privacy budget lower bound doubles with each time slot increasing until it reaches Ei /2 or a non-null publication occurs. For example, in Figure 19, assume α = 5, the non-null publication time slot is t6 . At time slot t1 , each ui ’s publication budget lower bound is Ei /(2wi ). Take u1 as an example: it reaches E1 /2 at time slot t4 . The publication lower bound for u1 remains at E1 /2 until time slot t6 . Let the publication

<err

(s,p)

NOP (sk) (w ) + NOP L

α+1 X

min

k=wL +1

2 2 ,Z + 2 ϵ2 ϵ L̃

!

R̃

2 2 (sk) =err (w ) + (α − wL + 1) min ,Z + 2 NOP L ϵ2 ϵ L̃ R̃ ! 2 2 2 2 < min H , w L Z + 2 Hw L ϵ2L wL ϵR ! 2 2 ,Z + 2 . + (α − wL + 1) min 2 ϵ ϵ L̃

!

(21)

R̃

Therefore, we obtain the average error upper bound errNOP for each time slot in PartNOP as   1 (s,p) errNOP < ef rrNOP + α · errnlf , (22) 2α + 1 (s,p)

where ef rrNOP is the value derived in Equation (21). When PartDC is private, its error is identical to that in PBD:   8 8 errDC < min , Z + . (23) d2 ϵ2L d2 ϵ2R Based on Equations (23), (20) and (22), we can derive the average error upper bound for each time slot in PBA as:     8 8 1 (s,p) min , Z + + ef rrNOP + α · errnlf , 2 2 2 2 d ϵL d ϵR 2α + 1 (s,p)

Fig. 19: An example of the publication budget lower bound in PBA.

where ef rrNOP is the final result from Equation (19) when α ≤ wL , and from Equation (21) when α > wL .

Leilei Du1 et al.

30

²L(B, M) (i) ²R(B, M) (i)

²F,(2)i, t (i)

(24) When PartDC is private, the error from PartDC will lead to falsely skipping or publishing a non-null publication. Both cases are bounded (1) by the error in PartDC . Let ϵ̂k be the privacy budget usage at time slot k in PartDC . For the error in PartDC , we have

$



EXGJHWYDOXHV

²F,(2,i,Lt) (i) ²F,(2,i,Rt) (i)

 )



%

.





,



+

'







QRQQXOOSXEOLFDWLRQWLPHV

* / ( &

errPartDC =

≤ min

(2,L)

2

2 ′ ,Z + 2 d2 (min(ϵFLL , ϵBL ))2 d (max(ϵFLR , ϵBR ))2

! .

(25)

Fig. 20: An example of backward privacy budget bounds, where (B,M) (B,M) ϵL (i) and ϵR (i) represent the lower and upper bounds of (2)

ŝ   1 Y X (1) · ef rrO ϵ̂k Y ŝ k=1

(2,R)

ϵB,i,t respectively, ϵF,i,t (i) and ϵF,i,t (i) represent the lower and (2)

Thus according to Equation (25) and (24), we can get the error of DPBD as errDPBD = errPartDC + errPartNOP .

upper bounds of budget values, and ϵF,i,t (i) shows an example of budget values.

8.5.4 Proof for Theorem 10

8.5.3 Proof for Theorem 9

Proof Let ρsk be the number of skipped publications before a nonnull publication and ρnu be the number of nullified publications after a non-null publication. When the process of PartDC is not private, the average error is only from PartNOP which can further divided into skipped publication error, non-null publication error and nullified publication error. E Let ϵFL (i) = mint 2wF,i,t , ϵFLL = mini∈[n] ϵFL (i) and ϵFLR = F,i,t maxi∈[n] ϵFL (i). Similar as that in the proof of Theorem 5, the publication lower bound doubles with the time slot increases. For each ui , (B,M) (i) ϵ let λL (i) = ϵL (i)/2 be the number of skipped time slots whose

Proof When PartDC is not private, the error of DPBD   is from the pro(2) (2) (2) cess of PartNOP . This error is determined by ϵt = ϵ1,t , . . . , ϵn,t (2)

(2)

at each time slot t, where each element ϵi,t depends on ϵB,i,t and (2)

(2)

(2)

ϵF,i,t . For any ϵB,i,t , there are two possible cases: either ϵF,i,t ≥ (B,M) (2) (B,M) ϵL (i) (as shown by Curve AHI in Figure 20) or ϵF,i,t < ϵL (i) (as shown by Curve IJ in Figure 20). Let γi be the number of non(B,M) (2) (i). Since the current backnull publications where ϵF,i,t ≥ ϵL (B,M) (B,M) (i), ϵR (i)], ward privacy budget can be any value within [ϵL we bound the transition point γi by considering the two extreme decay

cases of the forward budget: the fastest decay with per-publication con(B,M) sumption ϵR (i), and the slowest decay with per-publication con(B,M) (i). Therefore, after γi non-null publications, the forsumption ϵL (B,M) ward budget needs to be no greater than ϵL (i) in the fastest-decay (B,M) case, and no smaller than ϵR (i) in the slowest-decay case. Thus, we have (F )

EL (i) (B,M) (B,M) − γi · ϵR (i) ≤ ϵR (i); 2

FL

FL

(F )

err <

ŝ X

=

  1 Y (2) · ef rrO ϵ̂k Y ŝ k=1

=

1 ŝ

  (2) ef rrO ϵ̂k +

k=1

γR X k=γL +1

′

2γL 2γL Z γL , + 2 ŝϵ2 ŝ ŝϵ BL BR

  (2) ef rrO ϵ̂k +

ŝ X

  (2) ef rrO ϵ̂k

!

k=γR +1

!

 min

2 ′ ,Z + (kϵFLL )2 (kϵFLR )2 2



sk +1]   2 2 2 ′ 2 < min Hρ +1 , Z (ρsk + 1) + 2 Hρ +1 . 2 sk sk ϵ ϵ FLL FLR

If λLR < λRL , errPart can be classified into three cases that ρsk + NOP 1 ≤ λL , λL < ρsk + 1 ≤ λR and ρsk + 1 > λR . We denote the (s,p) (s,p,1) (s,p,2) (s,p,3) errPart as errPart , errPart and errPart respectively. NOP NOP NOP NOP (1) ρsk + 1 ≤ λL . In this case, the publication privacy budget lower bounds are determined by the forward publication privacy budget lower bounds. The publication privacy budget upper bounds are determined by the backward publication privacy budget upper bounds. Thus, we have

!

+ min

2(γR − γL ) Z ′ (γR − γL ) 32(4γR −γL − 1) , + 2 ŝϵ ŝ 3ŝϵ2 BL BR

32(4ŝ−γR − 1) Z ′ (ŝ − γR ) 32(4ŝ−γL − 4γR −γL ) , + 2 3ŝϵ ŝ 3ŝϵ2 BL BR

!

+ min

2(4ŝ−γR +2 + 3γR − 16) 2(4ŝ−γL +2 + 3γL − 16) ′ ,Z + 3ŝϵ2 3ŝϵ2 BL BR

!

≤ min

PartNOP X

(s,p)

errPartNOP

≤ min

(s,p)

k∈[ρ

(2) Let ϵ̂k be the privacy budget usage at time slot k in PartNOP . Then for the average error errPartNOP of PartNOP in DPBD, we have

γL X

(B,M)

bound are no more than ϵR (i). Let λLR = maxi∈[n] λL (i) be the maximal value among all λL (i). Let λRL = mini∈[n] λR (i) be the minimal value among all λR (i). If λLR ≥ λRL , then the publication privacy budget lower bounds and upper bounds are determined by the (s,p) forward publication budgets. Thus, for the error errPart in skipped NOP publications and non-null publication, we have

EL (i) (B,M) (B,M) − γi · ϵ L (i) ≥ ϵL (i). 2

Thus, 2ηi −1 − 1 ≤ γi ≤ 2βi −1 − 1.

(B,M)

(i). Let λR (i) = publication lower bound are no more than ϵL B,M) ( ϵR (i) be the number of skipped time slots whose publication lower ϵ (i)/2

err <

(s,p,1) PartNOP X

k∈[ρ

.

< min

2

min

(kϵFLL

sk +1] 2 ϵ2

FLL

2

Hρ

sk

′

)2

,Z +

2

!

ϵ2

BR

2(ρsk + 1) ′ +1 , Z (ρsk + 1) + 2 ϵ

BR

! .

Personalized w-Event Privacy for Infinite Stream Estimation

31

(2) λL < ρsk + 1 ≤ λR . In this case, the first λL publication privacy budget errors are the same as those in case (1). For the remaining errors, the publication privacy budget lower bounds and upper bounds are determined by the backward publication privacy budget lower bounds and upper bounds. Thus, we have err

(s,p,2) PartNOP ρ

< err

(s,p,1) (λ ) + PartNOP L

< min

sk +1 X

2

min

k=λL +1

2

2λL 2 ′ Hλ , Z λL + 2 L ϵ2 ϵ FLL BR 2

+ (ρsk − λL + 1) min

ϵ2 BL

BL !

!

ϵ2

BR

!

2

′

,Z +

2

′

,Z +

ϵ2

ϵ2 BR

.

(3) ρsk + 1 > λR . In this case, the first λR publication privacy budget errors are the same as those in case (2). For the remaining errors, the publication privacy budget lower bounds are determined by the backward publication privacy budget lower bounds. The publication privacy budget upper bounds are determined by the forward publication privacy budget upper bounds. Thus, we have err

(s,p,3) PartNOP ρ

< err

(s,p,2) (λ ) + PartNOP R

< min

sk +1 X

2

min

ϵ2

BL

k=λR +1

2λL 2 2 ′ Hλ , Z λL + 2 L ϵ2 ϵ FLL BR

+ (λR − λL ) min

2 ϵ2

′

,Z +

!

2

′

,Z +

(kϵFLR

)2

!

2

!

ϵ2

BL BR 2(ρsk − λR + 1) ′ + min , (ρsk − λR + 1)Z ϵ2 BL  2 2 Hρ −λ +1 . + 2 R sk ϵ FLR 

(s,p)

(s,p)

We denote the upper bound of errPart as ef rrPart . Therefore, NOP NOP we can get the average error upper bound errPartNOP of each time slot in PartNOP as errPartNOP <

  1 (s,p) + ρnu errnlf . ef rrPart NOP ρsk + ρnu + 1

(26)

When PartDC is private, the average error errPartDC from PartDC is the same as that in Theorem 9 (same as Equation (25)). From Equations (25) and (26), we can get the average error of DPBA as the sum of Equations (25) and (26).

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181