Boosting the Accuracy of Differentially Private Histograms Through Consistency

Summary: Selects a tuned set of histogram queries and enforces consistency on the noisy DP output, then projects to the nearest consistent input. This post-processing yields higher accuracy for DP histograms, enabling precise degree-sequence estimation and accurate range queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10146
Venue: VLDB
Year: 2010
Pagerank: 0.00037697111
Overall Rank: 178 | 98.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 72 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
715	Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption	2010	SIGMOD	0.00017725693
719	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00017626484
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
1,143	Privacy Preserving Vertical Federated Learning for Tree-based Models	2020	VLDB	0.00013710269
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,567	PrivBasis: Frequent Itemset Mining with Differential Privacy	2012	VLDB	0.0001133268
1,681	GUPT: Privacy Preserving Data Analysis Made Easy	2012	SIGMOD	0.00010929746
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
1,764	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010636626
1,891	Towards Model-based Pricing for Machine Learning in a Data Marketplace	2019	SIGMOD	0.00010194092
1,935	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010032967
2,052	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB	9.676612e-05
2,082	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.5834599e-05
2,226	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.2421776e-05
2,227	Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies	2014	SIGMOD	9.2421238e-05
2,274	An Adaptive Mechanism for Accurate Query Answering under Differential Privacy	2012	VLDB	9.1297703e-05
2,408	Estimating Numerical Distributions under Local Differential Privacy	2020	SIGMOD	8.8780076e-05
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
2,555	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD	8.5477878e-05
2,776	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1326122e-05
2,806	CryptEpsilon: Crypto-Assisted Differential Privacy on Untrusted Servers	2020	SIGMOD	8.0911177e-05
2,881	Data Synthesis via Differentially Private Markov Random Fields	2021	VLDB	7.9665978e-05
3,068	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD	7.6171639e-05
3,097	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	7.5647028e-05
3,368	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	7.1714763e-05
3,399	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.1408089e-05
3,907	DPT: Differentially Private Trajectory Synthesis Using Hierarchical Reference Systems	2015	VLDB	6.6395929e-05
4,189	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS	6.3743594e-05
4,252	DPSynthesizer: Differentially Private Data Synthesizer for Privacy Preserving Data Sharing	2014	VLDB	6.3233894e-05
4,461	Pufferfish Privacy Mechanisms for Correlated Data	2017	SIGMOD	6.1616828e-05
4,502	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.1366984e-05
4,600	Functional Mechanism: Regression Analysis under Differential Privacy	2012	VLDB	6.0578625e-05
5,267	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB	5.5972313e-05
5,545	Differential Privacy in the Wild: A tutorial on current practices & open challenges	2016	VLDB	5.4462098e-05
5,687	Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges	2017	SIGMOD	5.3706593e-05
5,752	PrivGene: Differentially Private Model Fitting Using Genetic Algorithms	2013	SIGMOD	5.340562e-05
6,185	Privacy-Aware Data Management in Information Networks	2011	SIGMOD	5.1666285e-05
6,486	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.0445043e-05
6,691	Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms	2013	SIGMOD	4.9613269e-05
6,887	Synthesizing Linked Data Under Cardinality and Integrity Constraints	2021	SIGMOD	4.8937852e-05
7,034	A Neural Database for Differentially Private Spatial Range Queries	2022	VLDB	4.8550912e-05
7,196	Longshot: Indexing Growing Databases using MPC and Differential Privacy	2023	VLDB	4.8036487e-05
7,313	Pythia: Data Dependent Differentially Private Algorithm Selection	2017	SIGMOD	4.7651627e-05
7,439	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD	4.7304034e-05
7,471	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	4.7199888e-05
7,619	Budget Sharing for Multi-Analyst Differential Privacy	2021	VLDB	4.6941145e-05
7,624	A Neural Approach to Spatio-Temporal Data Release with User-Level Differential Privacy	2023	SIGMOD	4.6931334e-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
83	Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis	2009	SIGMOD	0.00053933811
111	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00047073785

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
642	Private Analysis of Graph Structure	2011	VLDB	0.00018755196
8,418	Differentially Private Hierarchical Count-of-Counts Histograms	2018	VLDB	4.5183077e-05
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
11,879	Design of Policy-Aware Differentially Private Algorithms	2016	VLDB	4.1945683e-05
7,579	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS	4.706055e-05
10,348	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS	4.1945683e-05
1,935	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010032967
719	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00017626484
2,226	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.2421776e-05
10,513	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.1945683e-05