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: 10685
Venue: VLDB
Year: 2012
Pagerank: 9.1553397e-05
Overall Rank: 2,108 | 85.54%
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
567	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016420715
1,169	PrivBayes: Private Data Release via Bayesian Networks	2014	SIGMOD	0.00011838753
1,220	Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets	2014	VLDB	0.00011619529
1,308	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011216361
1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010548904
1,583	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010292522
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
4,302	Pufferfish Privacy Mechanisms for Correlated Data	2017	SIGMOD	6.7720437e-05
4,361	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.7443476e-05
6,441	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.8779245e-05
6,951	RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy	2025	SIGMOD	5.7303405e-05
7,850	Differentially Private Data Release over Multiple Tables	2023	PODS	5.5316993e-05
7,898	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	5.5196369e-05
7,968	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	5.516666e-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
62	Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis	2009	SIGMOD	0.00038970535
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031639377
130	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030604781
611	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00015747402
775	Differentially Private Data Cubes: Optimizing Noise Sources and Consistency	2011	SIGMOD	0.00014110531
2,799	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1125988e-05

Semantically Similar Papers

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