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: 9911
Venue: VLDB
Year: 2008
Pagerank: 7.0083453e-05
Overall Rank: 3,935 | 73.01%
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
517	Query by Output	2009	SIGMOD	0.00017169735
2,167	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB	9.047803e-05
8,784	Data Publishing against Realistic Adversaries	2009	VLDB	5.3736002e-05
12,460	Secure Personal Data Servers: a Vision Paper	2010	VLDB	5.093636e-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
70	Privacy-Preserving Data Mining	2000	SIGMOD	0.0003804755
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
130	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030604781
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
510	Practical Privacy: The SuLQ Framework	2005	PODS	0.00017220509
1,074	Privacy Preserving OLAP	2005	SIGMOD	0.0001230007
1,636	Relaxing Join and Selection Queries	2006	VLDB	0.00010156479
1,746	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.8564338e-05
2,401	Simulatable Auditing	2005	PODS	8.6299652e-05
3,296	Towards Robustness in Query Auditing	2006	VLDB	7.5459953e-05
6,571	Query Relaxation Using Malleable Schemas	2007	SIGMOD	5.8374223e-05

Semantically Similar Papers

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