An Adaptive Mechanism for Accurate Query Answering under Differential Privacy

Summary: Introduces an adaptive DP mechanism that selects strategy queries tailored to a workload, approximating the optimal strategy for linear counting queries. It substantially improves utility over prior methods and achieves near-optimal error under (ε,δ)-DP without requiring users to design the strategy. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h157f8117bd58bd11
Venue: VLDB
Year: 2012
Pagerank: 8.967065e-05
Overall Rank: 2,142 | 85.65%
DOI: 10.14778/2168651.2168653

Incoming Non-self Citations Over Time

Authors

1. Chao Li (University of Massachusetts Amherst)
2. Gerome Miklau (University of Massachusetts Amherst)

BibTeX Citation

@article{li_vldb12,
        title = {{An Adaptive Mechanism for Accurate Query Answering under Differential Privacy}},
        author = {Li, Chao and Miklau, Gerome},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {6},
        pages = {514--525},
        doi = {10.14778/2168651.2168653},
        url = {https://doi.org/10.14778/2168651.2168653},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
559	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016409103
1,160	PrivBayes: Private Data Release via Bayesian Networks	2014	SIGMOD	0.00011733273
1,249	Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets	2014	VLDB	0.00011336311
1,334	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00010981739
1,533	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010310932
1,620	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010041603
2,099	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.0315525e-05
2,315	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.6412356e-05
3,922	Pufferfish Privacy Mechanisms for Correlated Data	2017	SIGMOD	6.9051301e-05
4,434	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.5862354e-05
6,576	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.7255624e-05
7,117	RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy	2025	SIGMOD	5.580601e-05
8,030	Differentially Private Data Release over Multiple Tables	2023	PODS	5.3871505e-05
8,083	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	5.3754333e-05
8,156	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	5.3727254e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.00038378358
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00030972849
134	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00029947443
629	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00015421536
801	Differentially Private Data Cubes: Optimizing Noise Sources and Consistency	2011	SIGMOD	0.00013824207
2,863	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	7.9091713e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,338	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD
2	1,998	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB
3	8,156	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB
4	7,463	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS
5	6,677	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD
6	9,815	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB
7	9,816	Multi-Analyst Differential Privacy for Online Query Answering	2023	VLDB
8	1,533	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
9	629	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS
10	8,083	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB