💻 computer science

DP-S4S: Accurate and Scalable Select-Join-Aggregate Query Processing with User-Level Differential Privacy

The paper proposes DP-S4S, a novel mechanism that achieves scalable and accurate Select-Join-Aggregate query processing under user-level differential privacy by sampling aggregation units instead of users and establishing a sampling-friendly mathematical foundation based on RDP, thereby overcoming the prohibitive computational costs and high error rates of existing state-of-the-art methods.

Original authors: Yuan Qiu, Xiaokui Xiao, Yin Yang

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuan Qiu, Xiaokui Xiao, Yin Yang

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

Imagine you are the manager of a massive, bustling city (the Database). You want to ask the citizens (the Users) some questions to understand the city better, like "How many people bought coffee today?" or "How many friends does the average person have?"

However, there's a catch: you must answer these questions without revealing anything about any single specific person. This is the promise of Differential Privacy (DP). It's like adding a little bit of "static" or "noise" to the answer so that if you look at the result, you can't tell if Person A was in the crowd or not.

The paper introduces a new, super-smart way to do this called DP-S4S. Here is how it works, broken down with simple analogies.

The Problem: The "Heavy Lifter" and the "Expensive Calculator"

In the past, trying to answer these questions while protecting privacy was like trying to count every single grain of sand on a beach while wearing a blindfold and heavy gloves.

The "Heavy Lifter" (High Sensitivity): In a city, one person might have thousands of connections (friends, purchases, posts). If you remove just one person from your data, the total count could change wildly. To protect that one person, you have to add a huge amount of noise to the answer. This makes the answer very inaccurate (like trying to guess the temperature with a thermometer that is off by 50 degrees).
The "Expensive Calculator" (Slow Speed): To fix the accuracy issue, previous methods tried to solve incredibly complex math puzzles (optimization programs) to figure out exactly how much noise to add. It was like using a supercomputer to count the grains of sand one by one. It was accurate, but it took forever and cost a fortune in computing power.

The Old "Sampling" Attempt: The Flawed Shortcut

People realized, "Hey, why not just look at a small sample of the city instead of the whole thing?" This is called sampling.

However, the old way of doing this (called S&E) was like this:

You pick a random person.
You then interview that person and everyone they know.
You repeat this many times.

The Flaw: If you pick a popular person (a "celebrity" with 5,000 friends), you end up interviewing 5,000 people at once. This creates a massive correlation. To protect the privacy of that one celebrity, you have to add so much noise that the final answer is garbage. It's like trying to hear a whisper in a stadium because you accidentally picked the loudest person in the crowd.

The New Solution: DP-S4S (The "Smart Scout")

The authors propose DP-S4S (Differentially Private Sampling for Scale). Think of this as a team of Smart Scouts instead of a single heavy lifter.

1. Sampling the "Events," Not the "People"

Instead of picking a person and dragging their whole social circle into the interview, DP-S4S picks individual events (like a single coffee purchase or a single friendship link) at random.

Analogy: Imagine you want to know how many people are eating pizza.
- Old Way (S&E): Pick a person named "Big Bob." If Bob has 100 friends, you interview Bob and all 100 friends. If Bob is a privacy risk, you have to scramble the data for all 100 people.
- DP-S4S Way: You walk into the city and randomly pick 1,000 slices of pizza off plates. You don't care who ate them; you just count the slices. If a slice belongs to a "Big Bob," it's just one slice among many. The risk is spread out, so you don't need to add as much noise.

2. The "Privacy Amplifier"

Here is the magic trick. Because the scouts are picking individual slices (events) randomly, the privacy protection actually gets stronger the more you sample.

Analogy: Imagine you are hiding a secret in a haystack.
- If you hide it in a small haystack, it's easy to find.
- If you hide it in a giant haystack, it's hard to find.
- DP-S4S realizes that by randomly picking slices, the "haystack" effectively becomes bigger and more confusing to an attacker. This allows them to use less noise while keeping the same level of privacy. It's like getting a discount on the "privacy tax."

3. The "Mathematical Bridge" (Rényi DP)

To make this work for complex questions (like "Count the pizza slices for every neighborhood"), the authors built a new mathematical bridge. They used a specific type of privacy math called Rényi Differential Privacy.

Analogy: Think of standard privacy math as a rigid, heavy door. It's hard to open and close quickly. Rényi DP is like a sliding glass door. It's much easier to combine with the "sampling" process, allowing the system to slide smoothly between "looking at a sample" and "protecting privacy" without getting stuck.

The Results: Fast, Accurate, and Scalable

The paper tested this on real-world data (like social networks and shopping records) and found:

Speed: It is 10 to 100 times faster than the old methods. It can answer questions on massive datasets in seconds that used to take hours.
Accuracy: It is 10 times more accurate than the old "sampling" method (S&E). The answers are much closer to the truth.
Scalability: It can handle huge databases that would crash the old systems.

Summary

DP-S4S is like upgrading from a slow, clumsy giant trying to count every grain of sand to a fleet of agile drones that randomly sample the beach. By focusing on the individual grains (events) rather than the people holding them, and using a smarter mathematical framework, it delivers answers that are fast, cheap, and incredibly accurate, all while keeping everyone's secrets safe.

1. Problem Statement

The paper addresses the challenge of answering Select-Join-Aggregate (SJA) queries under User-Level Differential Privacy (DP).

Context: SJA queries are fundamental in data analytics (e.g., social network analysis, e-commerce reporting), involving selections, joins, and aggregations (COUNT, SUM, etc.).
The Privacy Constraint: Unlike record-level DP, User-Level DP protects the entire set of records contributed by a single user. This is crucial when users contribute multiple correlated records (e.g., a user's entire purchase history or social connections).
The Core Challenge:
1. High Sensitivity: A single user can contribute a massive number of join tuples. In worst-case scenarios, the global sensitivity of an SJA query can be exponential in the number of joins, requiring prohibitive amounts of noise to satisfy DP, which destroys result utility.
2. Scalability of Existing Solutions: State-of-the-art methods like R2T (for scalar queries) and PMSJA (for vector queries) achieve instance-optimal accuracy by solving expensive optimization problems (Linear Programs or Quadratically Constrained Quadratic Programs). These do not scale to large datasets.
3. Failure of Naive Sampling: Existing sampling approaches like S&E (Sample-and-Explore) sample users and then explore their neighbors. This fails because:
  - It requires knowing a bound on the number of collaborators ( $C$ ), which is often large.
  - The privacy analysis demands injecting significantly more noise (linear in $C$ ), leading to errors 10x–1000x higher than non-sampling methods.
  - It is unclear what to sample to maximize accuracy within a computational budget.

2. Methodology: DP-S4S

The authors propose DP-S4S (Differentially Private Sampling for Scale), a novel mechanism that fundamentally changes the sampling paradigm and the mathematical framework.

A. Core Innovation: Sampling Aggregation Units

Instead of sampling users (as in S&E), DP-S4S samples aggregation units (i.e., the join tuples resulting from the join operation).

Mechanism: The system first computes the full join result (or a subset), then samples each join tuple with probability $q$ .
Benefit: This keeps the sample set compact and avoids the "worst-case cross-user correlations" inherent in user-based sampling. It effectively decouples the sampling process from the user's total contribution size.

B. Privacy Amplification via Subsampling

The paper proves that sampling join tuples followed by a user-level DP mechanism on the sample provides privacy amplification.

Scalar Queries (Pure DP): By combining subsampling with the Truncation technique (capping user contributions), the mechanism achieves a stronger privacy guarantee ( $\epsilon'$ ) than the underlying mechanism ( $\epsilon$ ). The noise scale required is reduced because the probability of a specific user's data being in the sample is low.
Vector Queries (Approximate DP): For queries with GROUP BY clauses (vector outputs), the authors adapt the PMSJA framework. They introduce a new mathematical foundation using Rényi Differential Privacy (RDP) because RDP composes more cleanly with sampling than standard $(\epsilon, \delta)$ -DP.

C. Mathematical Infrastructure for Vector Queries

To handle vector queries efficiently, the authors develop two key theoretical tools:

Rényi DP Smooth Sensitivity Mechanism: They design the first mechanism that utilizes smooth sensitivity under Rényi DP. This allows the system to inject noise based on the local sensitivity of the truncated query (which is much smaller than global sensitivity) while maintaining rigorous privacy guarantees.
Adaptive Budget Allocation: The algorithm uses a "doubling search" strategy to select the optimal truncation threshold ( $\tau$ ) and the Rényi order ( $\alpha$ ) that minimizes error while satisfying the privacy budget.

D. Algorithm Flow

Sampling: Sample join tuples with probability $q$ .
Truncation & Optimization:
- Scalar: Solve a Linear Program (LP) to find the optimal truncation for the sample.
- Vector: Solve a Quadratically Constrained Quadratic Program (QCQP) on the sample to determine the truncation threshold using the Sparse Vector Technique (SVT).
Noise Injection: Add noise (Laplace for scalar, Gaussian/RDP for vector) calibrated to the sensitivity of the sampled and truncated data.
Scaling: Scale the result by $1/q$ to estimate the original query result.

3. Key Contributions

Novel Sampling Paradigm: The first mechanism to sample aggregation units (join tuples) rather than users for user-level DP, avoiding the high correlation and privacy costs of user-based sampling.
Theoretical Guarantees:
- Proven privacy amplification for user-level DP when sampling join tuples.
- Derivation of the first Smooth Sensitivity mechanism under Rényi DP, enabling efficient noise calibration for vector queries.
Scalability: Replaces expensive global optimization (solving LPs/QCQPs on the full dataset) with optimization on a small, sampled subset, drastically reducing computational complexity.
Unified Framework: Handles both scalar (single value) and vector (GROUP BY) SJA queries under user-level DP.

4. Experimental Results

The authors evaluated DP-S4S against R2T, PMSJA, and S&E on real-world datasets (Deezer, Amazon, Stack Overflow, TPC-H).

Scalar Queries:
- Accuracy: DP-S4S matches the accuracy of the non-sampling state-of-the-art R2T (and sometimes exceeds it due to privacy amplification) while being significantly faster.
- Efficiency: On large datasets (e.g., Deezer triangle counting), DP-S4S reduced runtime from 30 minutes (R2T) to 36 seconds with only a marginal increase in error.
- Comparison with S&E: DP-S4S achieves 10x to 1000x lower error than S&E at the same sample rates. S&E's error grows linearly with the number of collaborators, whereas DP-S4S does not.
Vector Queries:
- Feasibility: PMSJA often runs out of memory or takes hours (e.g., >10,000 seconds) on large datasets. DP-S4S solves these queries in seconds to minutes.
- Accuracy: DP-S4S maintains high utility, significantly outperforming S&E (which often exceeds 100% error) and matching PMSJA's accuracy at a fraction of the computational cost.
Parameter Sensitivity: The mechanism is robust across varying privacy budgets ( $\epsilon$ ) and data characteristics (degree bounds).

5. Significance

Bridging the Gap: DP-S4S successfully bridges the gap between high utility (accuracy) and scalability (efficiency) for user-level DP, a problem where previous solutions forced a trade-off.
Practical Deployment: By enabling the processing of massive datasets (e.g., 24M+ records in TPC-H) under strict user-level privacy, it makes private analytics feasible for real-world applications like social network analysis and e-commerce reporting.
Theoretical Advancement: The introduction of the Rényi DP Smooth Sensitivity Mechanism is a significant theoretical contribution that extends beyond SJA queries, potentially benefiting other tasks like graph statistics release and machine learning gradient computation.
Superiority over S&E: The paper definitively demonstrates that user-level sampling must be done on tuples, not users, to avoid catastrophic privacy costs, correcting a flaw in previous literature.