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)
Incoming Non-self Citations Over Time
Authors
- 1. Chao Li (University of Massachusetts Amherst)
- 2. Michael Hay (University of Massachusetts Amherst)
- 3. Vibhor Rastogi (University of Washington)
- 4. Gerome Miklau (University of Massachusetts Amherst)
- 5. Andrew McGregor (University of Massachusetts Amherst)
BibTeX Citation
@inproceedings{li_pods10,
address = {New York, NY, USA},
series = {{PODS} '10},
title = {{Optimizing Linear Counting Queries Under Differential Privacy}},
url = {https://dl.acm.org/doi/10.1145/1807085.1807104},
doi = {10.1145/1807085.1807104},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Li, Chao and Hay, Michael and Rastogi, Vibhor and Miklau, Gerome and McGregor, Andrew},
year = {2010}
}Incoming Citations (Sorted by Pagerank)
Showing 38 of 38 citing papers.
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 121 | Boosting the Accuracy of Differentially Private Histograms Through Consistency | 2010 | VLDB | 0.0003107472 |
| 133 | Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release | 2007 | PODS | 0.00030046147 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,665 | Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy | 2023 | SIGMOD |
| 2 | 3,330 | Answering Range Queries Under Local Differential Privacy | 2019 | SIGMOD |
| 3 | 1,530 | A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy | 2014 | VLDB |
| 4 | 7,442 | A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries | 2022 | PODS |
| 5 | 9,783 | Answering Private Linear Queries Adaptively using the Common Mechanism | 2023 | VLDB |
| 6 | 2,091 | Optimizing error of high-dimensional statistical queries under differential privacy | 2018 | VLDB |
| 7 | 8,139 | Optimizing Fitness-For-Use of Differentially Private Linear Queries | 2021 | VLDB |
| 8 | 8,067 | A workload-adaptive mechanism for linear queries under local differential privacy | 2020 | VLDB |
| 9 | 1,991 | Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy | 2012 | VLDB |
| 10 | 2,129 | An Adaptive Mechanism for Accurate Query Answering under Differential Privacy | 2012 | VLDB |