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: 9.0009748e-05
Overall Rank: 2,126 | 85.71%
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
558	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016470707
1,155	PrivBayes: Private Data Release via Bayesian Networks	2014	SIGMOD	0.00011777587
1,240	Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets	2014	VLDB	0.00011378375
1,324	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011023355
1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010349919
1,609	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010079578
2,090	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.0657103e-05
2,298	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.6731734e-05
3,909	Pufferfish Privacy Mechanisms for Correlated Data	2017	SIGMOD	6.9313197e-05
4,412	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.6112155e-05
6,564	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.7472781e-05
7,092	RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy	2025	SIGMOD	5.601767e-05
8,008	Differentially Private Data Release over Multiple Tables	2023	PODS	5.4075828e-05
8,061	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	5.3958211e-05
8,133	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	5.3931029e-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.00038522486
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031089378
133	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.0003006035
625	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00015478765
800	Differentially Private Data Cubes: Optimizing Noise Sources and Consistency	2011	SIGMOD	0.00013875702
2,855	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	7.9391282e-05

Semantically Similar Papers

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