Output Perturbation with Query Relaxation

Summary: Proposes an output-perturbation method to build a private statistical database that answers aggregates under epsilon-differential privacy with substantially reduced computation. Adds a query-relaxation mechanism that eliminates the fixed query cap, enabling unlimited querying; experiments on real data demonstrate practical efficiency and maintained privacy. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4fa6b6d11af9febb
Venue: VLDB
Year: 2008
Pagerank: 6.8652975e-05
Overall Rank: 3,993 | 73.17%
DOI: 10.14778/1454159.1454168

Incoming Non-self Citations Over Time

Authors

1. Xiaokui Xiao (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@article{xiao_vldb08,
        title = {{Output Perturbation with Query Relaxation}},
        author = {Xiao, Xiaokui and Tao, Yufei},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {857--868},
        doi = {10.14778/1454159.1454168},
        url = {https://doi.org/10.14778/1454159.1454168},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
519	Query by Output	2009	SIGMOD	0.00016937515
2,091	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.0614187e-05
8,950	Data Publishing against Realistic Adversaries	2009	VLDB	5.25217e-05
12,757	Secure Personal Data Servers: a Vision Paper	2010	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
69	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037940729
122	Revealing Information while Preserving Privacy	2003	PODS	0.00030756232
133	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030046147
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019822444
520	Practical Privacy: The SuLQ Framework	2005	PODS	0.00016931295
1,097	Privacy Preserving OLAP	2005	SIGMOD	0.00012035305
1,643	Relaxing Join and Selection Queries	2006	VLDB	0.00010001728
1,782	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.6477589e-05
2,450	Simulatable Auditing	2005	PODS	8.4450717e-05
3,359	Towards Robustness in Query Auditing	2006	VLDB	7.3746967e-05
6,695	Query Relaxation Using Malleable Schemas	2007	SIGMOD	5.7045295e-05

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	9,173	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD
3	276	Towards Practical Differential Privacy for SQL Queries	2018	VLDB
4	7,442	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS
5	11,550	Personalized Truncation for Personalized Privacy	2024	SIGMOD
6	5,639	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB
7	3,359	Towards Robustness in Query Auditing	2006	VLDB
8	879	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS
9	122	Revealing Information while Preserving Privacy	2003	PODS
10	1,530	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB