💻 computer science

Personalized w-Event Privacy for Infinite Stream Estimation

This paper addresses the limitation of homogeneous privacy assumptions in existing stream estimation by proposing a framework for personalized $w$ -event differential privacy that utilizes novel mechanisms like Personalized Budget Distribution and Absorption to dynamically accommodate user-specific privacy preferences while significantly reducing estimation error.

Original authors: Leilei Du, Xu Zhou, Peng Cheng, Lei Chen, Xuemin Lin, Wei Xi, Kenli Li

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Leilei Du, Xu Zhou, Peng Cheng, Lei Chen, Xuemin Lin, Wei Xi, Kenli Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern digital world, our lives leave a trail of data points: where we go, what we buy, and how we move through time. To make sense of this flood of information, analysts often need to publish statistics about these activities, such as the number of people in a specific location at a given hour. However, releasing this data carries a risk. If the information is too precise, it can reveal the private habits of individuals, turning a general trend into a personal exposure. To solve this, scientists use a method called differential privacy. Think of it as adding a carefully measured amount of static to a radio signal; the static is just enough to hide the identity of any single listener, but the overall song remains clear enough to be understood.

For years, researchers have applied this static to data that flows continuously, like a live feed of traffic or video. A common approach, known as "event privacy," protects a user's data for a specific window of time, say the last few hours, rather than trying to hide their entire history. The standard rule for this protection has been a "one-size-fits-all" policy. Every person in the system is treated the same, with the same amount of static added to their data and the same time window applied. While this is simple to manage, it fails to respect the reality that people have different needs. A celebrity might need their location hidden for a long time to avoid being tracked, while a street performer might want their location shared widely to attract an audience. Forcing the same level of protection on both creates a problem: the celebrity might still be at risk, or the performer's data might be so obscured by static that it becomes useless.

A team of researchers has addressed this imbalance by developing a new system that allows each person to set their own privacy rules for these continuous data streams. Instead of a single global rule, their system lets every user decide how long their data should be protected and how strong that protection should be. The researchers found that by letting users customize these settings, they could significantly improve the quality of the data while still keeping everyone safe. In tests using real-world data, their new method reduced the error in the results by more than 60 percent compared to older, uniform methods. This means the data remains accurate enough to be useful for things like monitoring traffic or analyzing video, even while respecting the unique privacy desires of every single person involved.

The core of this work is a framework that manages these individual choices without breaking the system. The researchers realized that if everyone has a different rule, the computer cannot simply pick one rule to apply to everyone. Instead, it must constantly calculate a shared solution that satisfies every individual's specific request at every moment. They designed two main strategies to handle this. The first strategy, which they call a distribution method, carefully divides the available protection resources among the users, ensuring that no one runs out of privacy coverage. The second strategy, an absorption method, allows the system to be more flexible. It lets the system "borrow" protection from future moments to handle a sudden need in the present, or save up protection from the past to use later. This flexibility is crucial because data streams are not static; they change rapidly, and a user's need for privacy might change from one second to the next.

To make this work, the system uses a smart decision-making process. Before releasing any data, it checks how much the current situation differs from the last time data was released. If the change is small, the system skips releasing new data and simply repeats the last known value, which saves the privacy resources for when they are truly needed. If the change is large, it releases a new, protected version of the data. The researchers proved mathematically that this approach works for both fixed rules, where a user's needs stay the same, and dynamic rules, where a user can change their mind about their privacy needs at any time. In the dynamic case, the system must ensure that a decision made today does not accidentally violate a privacy promise made yesterday or a promise intended for tomorrow.

The results of this research show that personalization is not just a theoretical ideal but a practical way to get better data. When the researchers tested their methods on synthetic data and real-world datasets, the personalized approaches consistently outperformed the traditional, uniform methods. For instance, in one test with real data, the new dynamic method reduced the average error in the results by at least 62.7 percent compared to the standard method. In another test with synthetic data, the absorption method reduced errors by at least 53.6 percent. These numbers indicate that by tailoring the protection to the individual, the system produces a much clearer picture of the world. The data is less distorted by the noise added to protect privacy, allowing analysts to see trends more clearly without compromising the safety of the individuals who generated the data.

This work represents a shift from a rigid, uniform approach to a flexible, human-centric one. It acknowledges that privacy is not a single commodity but a spectrum of needs that varies from person to person and moment to moment. By building a system that can handle these variations, the researchers have shown that it is possible to have high-quality data analysis without forcing everyone into the same box. The system ensures that the privacy of a user who needs strong, long-term protection is not weakened, while also ensuring that a user who wants to share more information is not unnecessarily obscured. The findings suggest that in the future, data collection systems can be designed to be both highly accurate and deeply respectful of individual choice, creating a balance where utility and privacy reinforce rather than hinder each other.

Technical Summary: Personalized w-Event Privacy for Infinite Stream Estimation

1. Problem Definition

The paper addresses the challenge of estimating statistics from infinite data streams while protecting individual user privacy under Differential Privacy (DP). Existing methods for w-event privacy (protecting user data across a sliding window of $w$ consecutive time slots) typically enforce homogeneous requirements, applying a uniform privacy budget ( $\epsilon$ ) and window size ( $w$ ) to all users.

This "one-size-fits-all" approach is suboptimal for real-world scenarios where users have distinct privacy preferences. For instance, a celebrity may require strong protection (large $w$ , small $\epsilon$ ) for location data, while a street artist might prefer weaker protection to maximize visibility. Enforcing the strictest requirement for all users leads to excessive data error (low utility), while enforcing the weakest fails to protect sensitive users.

The paper formalizes two problem settings:

Fixed Personalized Setting (PWEPP-IDS): Each user $u_i$ has a static privacy requirement defined by a fixed window size $w_i$ and a fixed privacy budget $E_i$ .
Dynamic Personalized Setting (DPWEPP-IDS): Users can specify time-varying requirements. At each time slot $t$ , a user declares a backward requirement (window $w_{B,i,t}$ , budget $E_{B,i,t}$ ) covering the recent past, and a forward requirement (window $w_{F,i,t}$ , budget $E_{F,i,t}$ ) covering the upcoming future.

The core challenge is Online Feasibility: The system must release a single shared aggregate statistic at each time slot that simultaneously satisfies the heterogeneous, time-varying privacy constraints of all users, ensuring consistency with previously consumed budgets and feasibility for future requirements.

2. Methodology

The authors propose a unified framework that transforms heterogeneous user requirements into a valid system-level release decision. The framework consists of two main components: a Personalized Window Size Mechanism (PWSM) for the fixed setting and a Dynamic Personalized Window Size Mechanism (DPWSM) for the dynamic setting.

2.1 Core Components

Optimal Budget Selection (OBS): Given a set of heterogeneous privacy budgets, OBS selects an optimal threshold $\epsilon_{opt}$ that minimizes the total reporting error. The error comprises sampling error (from users with budgets below the threshold) and noise error (from the Laplace mechanism applied to the threshold).
Personalized Private Dissimilarity Measure: To decide whether to publish a new obfuscated statistic or reuse the last one (thereby saving budget), the system calculates the dissimilarity between the current data and the last publication. This calculation is performed privately using a portion of the privacy budget.
Adaptive Release Strategy: If the private dissimilarity exceeds the square root of the expected noise error, a new publication is released; otherwise, the system skips the release (null publication), approximating the current value with the last one.

2.2 Fixed Setting Solutions (PWSM)

For the fixed setting, the framework is instantiated with two mechanisms:

Personalized Budget Distribution (PBD):
- Splits each user's total budget $E_i$ into two halves: one for dissimilarity calculation and one for publication.
- The publication budget is distributed evenly across the window ( $E_i / 2w_i$ ).
- If a publication occurs, the remaining budget for the current window is adjusted. If the dissimilarity is low, the budget is saved for future slots.
Personalized Budget Absorption (PBA):
- Designed for smoother streams. It allows a publication at time $t$ to "borrow" budget shares from future time slots within the user's window.
- If a publication uses more than the average share, subsequent slots are "nullified" (skipped) to maintain the average budget constraint.
- This mechanism absorbs the cost of a high-utility release by skipping future low-utility releases.

2.3 Dynamic Setting Solutions (DPWSM)

For the dynamic setting, the framework generalizes to DPBD and DPBA. These mechanisms introduce Feasibility Conditions to handle time-varying constraints:

Backward Feasibility: The budget used at time $t$ must not exceed the remaining budget of the current backward window ( $E_{B,i,t}$ minus historical consumption).
Forward Feasibility: The budget used at time $t$ must not violate the forward privacy requirements declared at any previous time slot $\tau$ whose forward window covers $t$ .
Mechanism Logic:
- DPBD: Calculates the feasible budget upper bound for each user by taking the minimum of the backward remaining budget and the forward remaining budget (derived from all active forward windows). It then splits this feasible budget for dissimilarity and publication.
- DPBA: Extends the absorption logic to dynamic windows. It calculates a "forward nullified right border" for each user based on historical forward requirements. If the current time slot falls within this border, the release is skipped. Otherwise, it calculates the maximum absorbable budget from future slots while respecting all active forward constraints.

3. Key Contributions

Problem Formulation: The paper defines Dynamic Personalized w-Event Private Publishing for Infinite Data Streams (DPWEPP-IDS), generalizing the fixed personalized setting to allow time-varying backward and forward privacy requirements. It introduces the privacy notion $(\tau, w_B, w_F, E_B, E_F)$ -EPDP.
Online Feasibility Challenge: It identifies and addresses the novel challenge of maintaining online feasibility under heterogeneous, time-varying constraints where a single shared release must satisfy all users' overlapping windows.
Unified Framework: The authors propose a unified framework (PWSM/DPWSM) that converts heterogeneous personalized requirements into a shared release decision using Optimal Budget Selection (OBS) and adaptive release strategies.
Mechanisms:
- PBD & PBA: Solutions for fixed personalized settings.
- DPBD & DPBA: Solutions for dynamic personalized settings that rigorously enforce backward and forward feasibility.
Theoretical Guarantees: The paper provides proofs that all mechanisms satisfy the respective personalized differential privacy definitions and establishes theoretical upper bounds for the average error (utility).
Experimental Validation: Extensive experiments on real and synthetic datasets demonstrate that the proposed mechanisms significantly outperform classical homogeneous baselines (BD and BA) in terms of utility (reducing Average Mean Relative Error).

4. Experimental Results

The authors evaluated the mechanisms on both real-world and synthetic datasets.

Performance: The proposed methods consistently improved utility over classical homogeneous baselines.
- For real datasets, DPBD reduced the Average Mean Relative Error (AMRE) by at least 62.7% compared to the standard Budget Distribution (BD) method.
- For synthetic datasets, DPBA reduced the AMRE by at least 53.6% compared to the standard Budget Absorption (BA) method.
Scalability: Theoretical analysis indicates that the time complexity is linear with respect to the number of users ( $n$ ) and the maximum window size, making the approach scalable for large user populations.

5. Significance and Claims

The paper claims that its primary contribution lies not merely in replacing global parameters with personalized ones, but in constructing and maintaining a valid shared release budget under overlapping, heterogeneous, and time-varying constraints.

Generalization: The work extends the w-event privacy paradigm to a more general and practical setting where privacy preferences evolve over time.
Feasibility: It solves the non-trivial problem of ensuring that a single aggregate release remains consistent with both historical budget consumption and future privacy feasibility, a challenge absent in classical homogeneous w-event privacy.
Practicality: By allowing users to set different privacy levels, the system avoids the trade-off between "over-protecting" some users (causing high error) and "under-protecting" others. The results suggest that personalized mechanisms can achieve significantly higher data utility without compromising the specific privacy guarantees required by individual users.

The authors maintain that while the trusted curator assumption is standard for centralized stream release, the proposed mechanisms specifically address the gap in handling heterogeneous and dynamic privacy requirements, which existing centralized methods (like BD, BA, RescueDP, SPAS) do not support.