iReduct: Differential Privacy with Reduced Relative Errors

Summary: iReduct provides differential privacy with reduced relative errors by allocating noise adaptively across query results. A novel resampling-based correlated-noise technique improves utility for small vs large answers, demonstrated on marginals of multi-dimensional histograms with real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4447
Venue: SIGMOD
Year: 2011
Pagerank: 8.1125988e-05
Overall Rank: 2,799 | 80.80%
DOI: 10.1145/1989323.1989348

Incoming Non-self Citations Over Time

Authors

1. Xiaokui Xiao (Nanyang Technological University)
2. Gabriel Bender (Cornell University)
3. Michael Hay (Cornell University)
4. Johannes Gehrke (Cornell University)

BibTeX Citation

@inproceedings{xiao_sigmod11,
        title = {{iReduct: Differential Privacy with Reduced Relative Errors}},
        author = {Xiao, Xiaokui and Bender, Gabriel and Hay, Michael and Gehrke, Johannes},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989348},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989348},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,906	GUPT: Privacy Preserving Data Analysis Made Easy	2012	SIGMOD	9.5020196e-05
1,956	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB	9.4157042e-05
2,074	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.2192882e-05
2,108	An Adaptive Mechanism for Accurate Query Answering under Differential Privacy	2012	VLDB	9.1553397e-05
2,167	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.047803e-05
2,300	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.7833594e-05
2,818	CryptEpsilon: Crypto-Assisted Differential Privacy on Untrusted Servers	2020	SIGMOD	8.0932359e-05
3,871	DPT: Differentially Private Trajectory Synthesis Using Hierarchical Reference Systems	2015	VLDB	7.0581665e-05
5,555	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB	6.1774651e-05
6,376	DProvDB: Differentially Private Query Processing with Multi-Analyst Provenance	2023	SIGMOD	5.893174e-05
6,441	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.8779245e-05
9,602	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	5.2487195e-05
12,326	Publishing Microdata with a Robust Privacy Guarantee	2012	VLDB	5.093636e-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
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031639377
130	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030604781
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
611	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS	0.00015747402
757	Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption	2010	SIGMOD	0.00014306168
4,732	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB	6.5343833e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,198	Local Dampening: Differential Privacy for Non-numeric Queries via Local Sensitivity	2021	VLDB
2	6,666	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD
3	11,280	Confidence Intervals for Private Query Processing	2024	VLDB
4	4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB
5	10,335	A General Framework for Per-record Differential Privacy	2026	SIGMOD
6	2,167	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB
7	775	Differentially Private Data Cubes: Optimizing Noise Sources and Consistency	2011	SIGMOD
8	11,203	Personalized Truncation for Personalized Privacy	2024	SIGMOD
9	3,935	Output Perturbation with Query Relaxation	2008	VLDB
10	1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB