Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy

Summary: First practical differential privacy technique for answering a batch of correlated queries via a low-rank workload. LRM nears the DP lower bound for batch queries and significantly outperforms prior approaches (Matrix Mechanism, naive) on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10372
Venue: VLDB
Year: 2012
Pagerank: 9.676612e-05
Overall Rank: 2,052 | 85.73%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
719	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00017626484
1,446	PrivBayes: Private Data Release via Bayesian Networks	2014	SIGMOD	0.0001194108
1,520	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011535148
1,764	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010636626
1,935	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010032967
2,434	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	8.8278955e-05
2,465	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.7518123e-05
5,267	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB	5.5972313e-05
5,752	PrivGene: Differentially Private Model Fitting Using Genetic Algorithms	2013	SIGMOD	5.340562e-05
7,471	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	4.7199888e-05
7,997	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	4.6105691e-05
9,512	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	4.3335882e-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
136	Revealing Information while Preserving Privacy	2003	PODS	0.0004241101
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037697111
715	Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption	2010	SIGMOD	0.00017725693
742	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00017360873
878	Differentially Private Data Cubes: Optimizing Noise Sources and Consistency	2011	SIGMOD	0.00015702437
2,776	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1326122e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,393	PrivRM: A Framework for Range Mean Estimation under Local Differential Privacy	2025	SIGMOD	4.3441378e-05
3,368	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	7.1714763e-05
3,068	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD	7.6171639e-05
9,512	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	4.3335882e-05
10,521	RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy	2025	SIGMOD	4.1945683e-05
2,434	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	8.8278955e-05
2,274	An Adaptive Mechanism for Accurate Query Answering under Differential Privacy	2012	VLDB	9.1297703e-05
7,471	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	4.7199888e-05
1,935	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010032967
742	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00017360873