Residual Sensitivity for Differentially Private Multi-Way Joins

Summary: Proposes residual sensitivity, an instance-aware DP measure in multiway joins, reducing sensitivity by modeling join influence across data. First DP for multiway joins with low noise, fast computation, and DB integration, enabling a practical private query engine. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hc77128942f1a3165
Venue: SIGMOD
Year: 2021
Pagerank: 5.6756613e-05
Overall Rank: 6,808 | 54.25%
DOI: 10.1145/3448016.3452813

Incoming Non-self Citations Over Time

Authors

1. Wei Dong (Hong Kong University of Science and Technology)
2. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{dong_sigmod21,
        title = {{Residual Sensitivity for Differentially Private Multi-Way Joins}},
        author = {Dong, Wei and Yi, Ke},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452813},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452813},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,498	R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys	2022	SIGMOD	6.5733482e-05
6,507	DProvDB: Differentially Private Query Processing with Multi-Analyst Provenance	2023	SIGMOD	5.7582198e-05
6,665	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD	5.7147475e-05
7,442	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS	5.5241292e-05
8,013	Differentially Private Data Release over Multiple Tables	2023	PODS	5.4050229e-05
8,338	Continual Observation of Joins under Differential Privacy	2024	SIGMOD	5.3502656e-05
8,678	Fight Fire with Fire: Towards Robust Graph Neural Networks on Dynamic Graphs via Actively Defense	2024	VLDB	5.2892731e-05
8,890	DPXPlain: Privately Explaining Aggregate Query Answers	2023	VLDB	5.2542808e-05
9,354	DP-starJ: A Differential Private Scheme towards Analytical Star-Join Queries	2023	SIGMOD	5.1877346e-05
9,972	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	5.1014161e-05
10,416	Acyclic Graph Pattern Counting under Local Differential Privacy	2026	SIGMOD	4.9769913e-05
10,449	Differentially Oblivious Multi-way Join	2026	SIGMOD	4.9769913e-05
10,550	A General Framework for Per-record Differential Privacy	2026	SIGMOD	4.9769913e-05
10,592	N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics	2026	SIGMOD	4.9769913e-05
11,611	Confidence Intervals for Private Query Processing	2024	VLDB	4.9769913e-05
11,642	DOP-SQL: A General-purpose, High-utility, and Extensible Private SQL System	2024	VLDB	4.9769913e-05
11,691	Universal Private Estimators	2023	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
64	Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis	2009	SIGMOD	0.00038504258
133	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030046147
276	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.00022332903
558	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.0001646292
609	Private Analysis of Graph Structure	2011	VLDB	0.0001558459
854	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013435506
879	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00013293341
1,168	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00011725733
1,243	Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets	2014	VLDB	0.00011372988
1,250	No Free Lunch in Data Privacy	2011	SIGMOD	0.00011341376
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020376
1,610	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010074806
1,841	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.5270124e-05
2,012	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	9.190805e-05
2,488	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD	8.3933335e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	879	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS
2	276	Towards Practical Differential Privacy for SQL Queries	2018	VLDB
3	6,665	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD
4	7,299	Architecting a Differentially Private SQL Engine	2019	CIDR
5	1,168	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB
6	854	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD
7	2,488	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD
8	8,338	Continual Observation of Joins under Differential Privacy	2024	SIGMOD
9	8,013	Differentially Private Data Release over Multiple Tables	2023	PODS
10	10,449	Differentially Oblivious Multi-way Join	2026	SIGMOD