Optimizing Linear Counting Queries Under Differential Privacy

Summary: Introduce the matrix mechanism: answer workloads by privately answering a chosen strategy set with Laplace noise, then reconstructing workload answers to induce correlated noise and reduce error. Provide error analysis and show optimal strategy selection is a rank‑constrained semidefinite program, unifying prior methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1513
Venue: PODS
Year: 2010
Pagerank: 0.00017336928
Overall Rank: 742 | 94.85%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 38 of 38 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
451	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.00022807098
714	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00017670757
1,446	PrivBayes: Private Data Release via Bayesian Networks	2014	SIGMOD	0.00011931212
1,516	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011558246
1,607	Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets	2014	VLDB	0.00011171719
1,681	GUPT: Privacy Preserving Data Analysis Made Easy	2012	SIGMOD	0.00010922454
1,727	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010731889
1,762	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010629368
1,928	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010062105
2,061	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB	9.6578455e-05
2,278	An Adaptive Mechanism for Accurate Query Answering under Differential Privacy	2012	VLDB	9.1254873e-05
2,436	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	8.8217855e-05
2,461	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.7486072e-05
2,791	CryptEpsilon: Crypto-Assisted Differential Privacy on Untrusted Servers	2020	SIGMOD	8.1198086e-05
2,798	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1092023e-05
3,361	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	7.1718964e-05
4,461	Pufferfish Privacy Mechanisms for Correlated Data	2017	SIGMOD	6.1571961e-05
4,504	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.1307972e-05
4,602	Functional Mechanism: Regression Analysis under Differential Privacy	2012	VLDB	6.0520272e-05
5,494	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	5.4770961e-05
5,552	Differential Privacy in the Wild: A tutorial on current practices & open challenges	2016	VLDB	5.4413452e-05
5,700	Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges	2017	SIGMOD	5.3655082e-05
5,753	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB	5.33923e-05
5,765	PrivGene: Differentially Private Model Fitting Using Genetic Algorithms	2013	SIGMOD	5.3354212e-05
6,067	APEx: Accuracy-Aware Differentially Private Data Exploration	2019	SIGMOD	5.2241487e-05
6,480	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.0396886e-05
6,692	Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms	2013	SIGMOD	4.9568011e-05
6,901	Disclosure-Compliant Query Answering	2024	SIGMOD	4.8878659e-05
7,471	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	4.7158603e-05
7,501	PSynDB: Accurate and Accessible Private Data Generation	2019	VLDB	4.7135369e-05
7,620	Budget Sharing for Multi-Analyst Differential Privacy	2021	VLDB	4.6896122e-05
7,865	Differentially Private Data Release over Multiple Tables	2023	PODS	4.6282846e-05
7,875	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	4.6262777e-05
8,412	Differentially Private Hierarchical Count-of-Counts Histograms	2018	VLDB	4.5142126e-05
9,514	Multi-Analyst Differential Privacy for Online Query Answering	2023	VLDB	4.3294349e-05
10,530	RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy	2025	SIGMOD	4.1905499e-05
11,146	DP-PQD: Privately Detecting Per-Query Gaps In Synthetic Data Generated By Black-Box Mechanisms	2024	VLDB	4.1905499e-05
12,203	HOMES: A Higher-Order Mapping Evaluation System	2011	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
111	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00047047599
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037726596

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,437	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD	4.7258659e-05
3,073	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD	7.6098046e-05
1,928	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010062105
7,584	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS	4.7015411e-05
9,513	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	4.3294349e-05
2,436	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	8.8217855e-05
8,000	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	4.6061476e-05
7,471	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	4.7158603e-05
2,061	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB	9.6578455e-05
2,278	An Adaptive Mechanism for Accurate Query Answering under Differential Privacy	2012	VLDB	9.1254873e-05