Answering Private Linear Queries Adaptively using the Common Mechanism

Summary: Decomposes DP mechanisms for linear queries into a shared mechanism and mechanism-specific residuals. Conditioning selection on the shared output adaptively chooses an analysis while retaining the chosen mechanism’s full accuracy and privacy budget. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13232
Venue: VLDB
Year: 2023
Pagerank: 5.2487195e-05
Overall Rank: 9,602 | 34.13%
DOI: 10.14778/3594512.3594519

Incoming Non-self Citations Over Time

Authors

1. Yingtai Xiao (Pennsylvania State University)
2. Guanhong Wang (University of Maryland)
3. Danfeng Zhang (Pennsylvania State University)
4. Daniel Kifer (Pennsylvania State University)

BibTeX Citation

@article{xiao_vldb23,
        title = {{Answering Private Linear Queries Adaptively using the Common Mechanism}},
        author = {Xiao, Yingtai and Wang, Guanhong and Zhang, Danfeng and Kifer, Daniel},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {8},
        pages = {1883--1896},
        doi = {10.14778/3594512.3594519},
        url = {https://doi.org/10.14778/3594512.3594519},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,376	DProvDB: Differentially Private Query Processing with Multi-Analyst Provenance	2023	SIGMOD	5.893174e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031639377
281	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.00022445849
1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010548904
1,956	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB	9.4157042e-05
2,012	Understanding the Sparse Vector Technique for Differential Privacy	2017	VLDB	9.3073552e-05
2,167	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.047803e-05
2,300	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.7833594e-05
2,476	Data Synthesis via Differentially Private Markov Random Fields	2021	VLDB	8.5258582e-05
2,799	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1125988e-05
2,841	AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data	2022	VLDB	8.0637668e-05
4,732	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB	6.5343833e-05
5,055	APEx: Accuracy-Aware Differentially Private Data Exploration	2019	SIGMOD	6.3824509e-05
7,968	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	5.516666e-05
9,569	Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms	2020	VLDB	5.2528121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,956	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB
2	1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
3	7,639	Budget Sharing for Multi-Analyst Differential Privacy	2021	VLDB
4	9,604	Framework for Differentially Private Data Analysis with Multiple Accuracy Requirements	2021	SIGMOD
5	7,898	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB
6	6,534	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD
7	7,968	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB
8	611	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS
9	2,108	An Adaptive Mechanism for Accurate Query Answering under Differential Privacy	2012	VLDB
10	9,603	Multi-Analyst Differential Privacy for Online Query Answering	2023	VLDB