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.8439132e-05
Overall Rank: 4,008 | 73.14%
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
520	Query by Output	2009	SIGMOD	0.00016910379
2,099	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.0315525e-05
8,971	Data Publishing against Realistic Adversaries	2009	VLDB	5.2348031e-05
12,800	Secure Personal Data Servers: a Vision Paper	2010	VLDB	4.9605343e-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.00037815735
123	Revealing Information while Preserving Privacy	2003	PODS	0.00030654879
134	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00029947443
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
525	Practical Privacy: The SuLQ Framework	2005	PODS	0.00016875512
1,101	Privacy Preserving OLAP	2005	SIGMOD	0.00011995659
1,649	Relaxing Join and Selection Queries	2006	VLDB	9.9699016e-05
1,792	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.6159131e-05
2,457	Simulatable Auditing	2005	PODS	8.4172033e-05
3,370	Towards Robustness in Query Auditing	2006	VLDB	7.3503641e-05
6,692	Query Relaxation Using Malleable Schemas	2007	SIGMOD	5.6910171e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,677	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD
2	279	Towards Practical Differential Privacy for SQL Queries	2018	VLDB
3	9,198	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD
4	7,463	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS
5	11,599	Personalized Truncation for Personalized Privacy	2024	SIGMOD
6	5,652	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB
7	3,370	Towards Robustness in Query Auditing	2006	VLDB
8	880	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS
9	123	Revealing Information while Preserving Privacy	2003	PODS
10	1,533	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB