DP-S4S: Accurate and Scalable Select-Join-Aggregate Query Processing with User-Level Differential Privacy Journal: PACMMOD Volume: 4 3 (SIGMOD) 165 6 DOI: 10.1145/3802042 CCS: Security and privacy Differential privacy CCS: Information systems Database query processing CCS: Mathematics of computing Probability and statistics
Yuan Qiu, Xiaokui Xiao, Yin Yang · 2026
Read DP-S4S: Accurate and Scalable Select-Join-Aggregate Query Processing with User-Level Differential Privacy Journal: PACMMOD Volume: 4 3 (SIGMOD) 165 6 DOI: 10.1145/3802042 CCS: Security and privacy Differential privacy CCS: Information systems Database query processing CCS: Mathematics of computing Probability and statistics by Yuan Qiu, Xiaokui Xiao, Yin Yang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14994.txt.
Introduction
Qiu and co-authors tackle private Select-Join-Aggregate queries over large databases. Current methods protect each user, but they solve costly optimization problems. The team shows that a prior sampling method can err ten times more than the base mechanism. Their method, DP-S4S, samples aggregation units instead of users. It also builds new math for such queries under Renyi differential privacy. Tests on real data show it scales well while keeping results useful.
Catalog record
| CREATOR | Yuan Qiu, Xiaokui Xiao, Yin Yang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118853 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.14994
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DP-S4S: Accurate and Scalable Select-Join-Aggregate Query Processing with User-Level Differential Privacy Journal: PACMMOD Volume: 4 3 (SIGMOD) 165 6 DOI: 10.1145/3802042 CCS: Security and privacy Differential privacy CCS: Information systems Database query processing CCS: Mathematics of computing Probability and statistics Yuan Qiu, Xiaokui Xiao, Yin Yang Abstract . Answering Select-Join-Aggregate (SJA) queries with differential privacy (DP) is a fundamental problem with important applications in various domains. The current state-of-the-art methods ensure user-level DP (i.e., the adversary cannot infer the presence or absence of any given individual user with high confidence) and achieve instance-optimal accuracy on the query results. However, these solutions involve solving expensive optimization programs, which may incur prohibitive computational overhead for large databases. One promising direction to achieve scalability is through sampling, which provides a tunable trade-off between result utility and computational costs. However, applying sampling to differentially private SJA processing is a challenge for two reasons. First, it is unclear what to sample , in order to achieve the best accuracy within a given computational budget. Second, prior solutions were not designed with sampling in mind, and their mathematical tool chains are not sampling-friendly. To our knowledge, the only known solution that applies sampling to private SJA processing is S&E , a recent proposal that (i) samples users and (ii) combines sampling directly with existing solutions to enforce DP. We show that both are suboptimal designs; consequently, even with a relatively high sample rate, the error incurred by S&E can be 10x higher than the underlying DP mechanism without sampling. Motivated by this, we propose Differentially Private Sampling for Scale ( DP-S4S ), a novel mechanism that addresses the above challenges by (i) sampling aggregation units instead of users, and (ii) laying the mathematical foundation for SJA processing under Rényi-DP , which composes more easily with sampling. Further, DP-S4S can answer both scalar (e.g., COUNT, SUM, etc.) and vector (with GROUP BY predicts) SJA queries. Extensive experiments on real data demonstrate that DP-S4S enables scalable SJA processing on large datasets under user-level DP, while maintaining high result utility. † † cc-license: by 1. Introduction Differential privacy (DP) ( 12 ) provides a rigorous framework for releasing query results while protecting individuals’ privacy, by requiring outputs to remain statistically similar on any two neighboring datasets , so that the adversary cannot infer with high confidence which dataset was used to produce the outputs. The precise privacy guarantee depends on the definition of neighboring datasets. In a relational database, record-level DP considers two datasets as neighbors if they differ in exactly one record ( 14 ; 16 ; 34 ; 30 ; 19 ) . User-level DP , in contrast, treats two datasets as neighbors if they differ in the set of all the records contributed by one user ( 22 ; 15 ) . The latter, stronger notion is necessary when each user may contribute multiple, potentially correlated records, e.g., connections in a social network, purchase histories in an e-commerce platform, etc. This paper focuses on enforcing user-level DP when answering Select-Join-Aggregate (SJA) queries, which combine selection predicates, joins, and aggregation operators to capture a broad spectrum of reporting workloads, making them a central target for private query processing systems ( 23 ; 10 ) . A major challenge in processing SJA queries under user-level DP is that such a query often has a high sensitivity , meaning that adding or removing a user (which may lead to the addition or removal of many records) can significantly alter the query output. As we review in Section 2.1 , a high sensitivity necessitates large amounts of noise to be injected into the query result to satisfy DP, leading to poor result utility. To address this issue, state-of-the-art approaches to SJA processing under user-level DP (e.g., ( 9 ; 10 ) ) commonly employ a technique called truncation . The main idea is to impose a limit on the influence that any single user can have on the SJA query result. For instance, consider a simple query: edge counting in a social network, in which a user can have a large number of connections (e.g., up to 5,000 on Facebook ( 31 ) ). With truncation, the query engine can impose an upper bound, e.g., up to 10 edges are counted for each user, which reduces the query sensitivity dramatically, leading to a lower noise requirement to satisfy DP, as we explain in Section 2.1 . Truncation, however, also has a negative impact on query result accuracy, since it introduces a bias by capping the influence of every user. Thus, to design an effective truncation scheme that maximizes result utility, one must carefully balance the error due to truncation bias and the noise injected to satisfy DP, which is a non-trivial problem. Prior work R2T ( 9 ) addresses this by considering all possible truncation thresholds that are a power of two, which guarantees asymptotically optimal result accuracy, as we elaborate further in Section 2.3 . The downside of R2T , however, is that for each truncation threshold, it needs to solve a linear program to choose aggregation units to retain ( 22 ) . Since it is computationally expensive to solve so many linear programs, R2T does not scale well to large datasets ( 15 ) , as shown in our experiments in Section 5 . Further, R2T is limited to SJA queries with scalar outputs, i.e., each query returns a single numeric result. For SJA queries with vector outputs , e.g., those involving a GROUP BY clause, the best known solution to our knowledge is PMSJA ( 10 ) , which involves solving even more expensive quadratically constrained quadratic programs (QCQPs) ( 27 ; 29 ) , which exacerbates the scalability issue. A natural approach to improving efficiency is sampling, which enables the user to reach a desirable trade-off between query result accuracy and computational costs by choosing an appropriate sample size. Unfortunately, incorporating sampling into user-level private SJA processing is challenging, since (i) it is unclear what objects should be sampled to stay within a computational budget, and (ii) existing truncation-based pipelines are calibrated in the (\varepsilon,\delta) -DP model, which is not easy to compose with sampling. To our knowledge, the only user-level DP solution with sampling is S&E ( 15 ) , which (i) samples users and then extends the sample by exploring their neighboring records, and (ii) applies an existing solution such as R2T or PMSJA on the extended sample set. Since the sampled users may remain highly correlated, the privacy analysis demands injecting far more noise, yielding errors that can exceed those of R2T or PMSJA by more than an order of magnitude. This paper presents Differentially Private Sampling for Scale ( DP-S4S ), a mechanism that delivers user-level DP accuracy comparable to R2T and PMSJA while scaling to much larger databases. DP-S4S samples aggregation units (e.g., join tuples) instead of users, which keeps samples compact and avoids the worst cross-user correlations as in S&E . We show that the error introduced by sampling can be partially compensated for by its privacy amplification effect, which reduces the noise level to satisfy DP. Meanwhile, for vector SJA queries, we build new mathematical infrastructure to adapt