A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy

Summary: Data- and workload-aware algorithm for answering range queries under epsilon-DP. Privately learns a domain partition into data-tuned buckets and privately estimates bucket counts aligned to the workload, achieving substantially lower error than competing methods; validated on diverse real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10913
Venue: VLDB
Year: 2014
Pagerank: 0.00010062105
Overall Rank: 1,928 | 86.61%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,516	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011558246
1,740	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00010696383
2,224	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.256869e-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
3,361	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	7.1718964e-05
3,397	Automatic Data Repair: Are We Ready to Deploy?	2024	VLDB	7.1386386e-05
4,504	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.1307972e-05
5,264	PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy	2023	SIGMOD	5.5951175e-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
6,067	APEx: Accuracy-Aware Differentially Private Data Exploration	2019	SIGMOD	5.2241487e-05
6,886	Synthesizing Linked Data Under Cardinality and Integrity Constraints	2021	SIGMOD	4.8904572e-05
6,969	Architecting a Differentially Private SQL Engine	2019	CIDR	4.8749348e-05
7,034	A Neural Database for Differentially Private Spatial Range Queries	2022	VLDB	4.8504321e-05
7,311	Pythia: Data Dependent Differentially Private Algorithm Selection	2017	SIGMOD	4.7605916e-05
7,484	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB	4.7135369e-05
7,620	Budget Sharing for Multi-Analyst Differential Privacy	2021	VLDB	4.6896122e-05
7,626	A Neural Approach to Spatio-Temporal Data Release with User-Level Differential Privacy	2023	SIGMOD	4.6886327e-05
8,000	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	4.6061476e-05
8,073	Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures	2023	VLDB	4.5889649e-05
8,412	Differentially Private Hierarchical Count-of-Counts Histograms	2018	VLDB	4.5142126e-05
9,290	PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy	2024	VLDB	4.358174e-05
9,513	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	4.3294349e-05
9,592	HDPView: Differentially Private Materialized View for Exploring High Dimensional Relational Data	2022	VLDB	4.3161588e-05
11,384	MIDE: Accuracy Aware Minimally Invasive Data Exploration For Decision Support	2022	VLDB	4.1905499e-05
11,887	Design of Policy-Aware Differentially Private Algorithms	2016	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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.00053910987
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
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
742	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00017336928
872	Differentially Private Data Cubes: Optimizing Noise Sources and Consistency	2011	SIGMOD	0.00015702532
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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,361	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	7.1718964e-05
742	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00017336928
7,471	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	4.7158603e-05
11,887	Design of Policy-Aware Differentially Private Algorithms	2016	VLDB	4.1905499e-05
3,401	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.1343786e-05
1,383	A Privacy-Preserving Index for Range Queries	2004	VLDB	0.00012262651
3,073	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD	7.6098046e-05
2,461	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.7486072e-05
3,769	Output Perturbation with Query Relaxation	2008	VLDB	6.7744696e-05
2,278	An Adaptive Mechanism for Accurate Query Answering under Differential Privacy	2012	VLDB	9.1254873e-05