Back to papers
A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries
Summary: DP mechanism for conjunctive/graph-pattern counts achieving near-instance-optimal error (constant-factor relaxation of instance-optimality). Constructive algorithm with provable per-instance near-optimal error, replacing prior approaches lacking any optimality guarantees.
(summarized by gpt-5-mini on Feb 09 2026)
Paper ID
hb32973937a48bb51
Venue
PODS
Year
2022
Pagerank
5.505863e-05
Overall Rank
7,463 | 49.98%
DOI
10.1145/3517804.3524143
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_pods22,
address = {New York, NY, USA},
series = {{PODS} '22},
title = {{A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries}},
url = {https://dl.acm.org/doi/10.1145/3517804.3524143},
doi = {10.1145/3517804.3524143},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Dong, Wei and Yi, Ke},
year = {2022}
}
Incoming Citations (Sorted by Pagerank)
Showing 15 of 15 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
4,518
R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys 2022
SIGMOD
6.551704e-05
6,677
Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy 2023
SIGMOD
5.6958509e-05
7,626
Privacy Amplification by Sampling under User-level Differential Privacy 2024
SIGMOD
5.4657865e-05
8,030
Differentially Private Data Release over Multiple Tables 2023
PODS
5.3871505e-05
8,351
Continual Observation of Joins under Differential Privacy 2024
SIGMOD
5.3325743e-05
8,698
Fight Fire with Fire: Towards Robust Graph Neural Networks on Dynamic Graphs via Actively Defense 2024
VLDB
5.2717835e-05
8,910
DPXPlain: Privately Explaining Aggregate Query Answers 2023
VLDB
5.2369069e-05
9,380
DP-starJ: A Differential Private Scheme towards Analytical Star-Join Queries 2023
SIGMOD
5.1705808e-05
10,003
Secure Sampling for Approximate Multi-party Query Processing 2023
SIGMOD
5.0845476e-05
10,482
Acyclic Graph Pattern Counting under Local Differential Privacy 2026
SIGMOD
4.9605343e-05
10,515
Differentially Oblivious Multi-way Join 2026
SIGMOD
4.9605343e-05
10,615
A General Framework for Per-record Differential Privacy 2026
SIGMOD
4.9605343e-05
10,654
N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics 2026
SIGMOD
4.9605343e-05
11,658
Confidence Intervals for Private Query Processing 2024
VLDB
4.9605343e-05
11,737
Universal Private Estimators 2023
PODS
4.9605343e-05
Outgoing Citations (Sorted by Pagerank)
Showing 20 of 20 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
5
Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001
PODS
0.0010688884
134
Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release 2007
PODS
0.00029947443
279
Towards Practical Differential Privacy for SQL Queries 2018
VLDB
0.00022277389
357
FAQ: Questions Asked Frequently 2016
PODS
0.00020048899
559
Understanding Hierarchical Methods for Differentially Private Histograms 2013
VLDB
0.00016409103
612
Private Analysis of Graph Structure 2011
VLDB
0.00015534022
858
Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins 2013
SIGMOD
0.00013391977
880
Relationship Privacy: Output Perturbation for Queries with Joins 2009
PODS
0.00013249752
1,096
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017
PODS
0.00012035761
1,170
PrivateSQL: A Differentially Private SQL Query Engine 2019
VLDB
0.00011687052
1,249
Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets 2014
VLDB
0.00011336311
1,256
No Free Lunch in Data Privacy 2011
SIGMOD
0.00011304781
1,568
AJAR: Aggregations and Joins over Annotated Relations 2016
PODS
0.00010178045
1,620
PriView: Practical Differentially Private Release of Marginal Contingency Tables 2014
SIGMOD
0.00010041603
1,851
Publishing Graph Degree Distribution with Node Differential Privacy 2016
SIGMOD
9.4955175e-05
2,021
Private Release of Graph Statistics using Ladder Functions 2015
SIGMOD
9.160422e-05
2,497
Computing Local Sensitivities of Counting Queries with Joins 2020
SIGMOD
8.365674e-05
4,518
R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys 2022
SIGMOD
6.551704e-05
6,823
Residual Sensitivity for Differentially Private Multi-Way Joins 2021
SIGMOD
5.656894e-05
11,737
Universal Private Estimators 2023
PODS
4.9605343e-05
Semantically Similar Papers