Practical Privacy: The SuLQ Framework

Summary: Defines SuLQ: slightly noisy answers to a sublinear number of queries, extending privacy analysis to real-valued queries and arbitrary rows with tighter noise bounds. Shows SuLQ can implement PCA, k‑means, Perceptron, ID3 and most statistical‑query algorithms with few calls. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h25aa483b844cf716
Venue: PODS
Year: 2005
Pagerank: 0.00016931295
Overall Rank: 520 | 96.51%
DOI: 10.1145/1065167.1065184

Incoming Non-self Citations Over Time

Authors

1. Avrim Blum (Carnegie Mellon University)
2. Cynthia Dwork (Microsoft Research (Silicon Valley))
3. Frank McSherry (Microsoft Research (Silicon Valley))
4. Kobbi Nissim (Ben Gurion University)

BibTeX Citation

@inproceedings{blum_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Practical Privacy: The SuLQ Framework}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065184},
        doi = {10.1145/1065167.1065184},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Blum, Avrim and Dwork, Cynthia and McSherry, Frank and Nissim, Kobbi},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 30 of 30 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
64	Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis	2009	SIGMOD	0.00038504258
133	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030046147
558	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.0001646292
733	Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption	2010	SIGMOD	0.00014377067
1,250	No Free Lunch in Data Privacy	2011	SIGMOD	0.00011341376
1,453	PrivBasis: Frequent Itemset Mining with Differential Privacy	2012	VLDB	0.00010597751
1,610	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010074806
1,782	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.6477589e-05
2,371	Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies	2014	SIGMOD	8.5575829e-05
2,930	Privacy via Pseudorandom Sketches	2006	PODS	7.8380899e-05
3,125	Bayesian Differential Privacy on Correlated Data	2015	SIGMOD	7.6196809e-05
3,359	Towards Robustness in Query Auditing	2006	VLDB	7.3746967e-05
3,993	Output Perturbation with Query Relaxation	2008	VLDB	6.8652975e-05
4,041	Epistemic Privacy	2008	PODS	6.8354934e-05
4,420	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS	6.6042887e-05
4,664	Time Series Compressibility and Privacy	2007	VLDB	6.4782305e-05
5,443	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS	6.1254857e-05
5,687	Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges	2017	SIGMOD	6.0339826e-05
6,473	Differentially Private Vertical Federated Clustering	2023	VLDB	5.7713471e-05
6,501	Differential Privacy in the Wild: A tutorial on current practices & open challenges	2016	VLDB	5.7623453e-05
6,841	Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms	2013	SIGMOD	5.6653413e-05
6,964	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS	5.6302214e-05
7,634	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB	5.4788359e-05
7,669	Private Incremental Regression	2017	PODS	5.4746904e-05
8,370	Local Dampening: Differential Privacy for Non-numeric Queries via Local Sensitivity	2021	VLDB	5.3436e-05
9,173	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD	5.2126805e-05
9,271	Preserving Privacy and Fairness in Peer-to-Peer Data Integration	2010	SIGMOD	5.2032182e-05
9,548	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.159717e-05
9,674	Preservation of Proximity Privacy in Publishing Numerical Sensitive Data	2008	SIGMOD	5.142891e-05
11,094	Differentially Private Substring and Document Counting	2025	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
226	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00023973554
254	On the Design and Quantification of Privacy Preserving Data Mining Algorithms	2001	PODS	0.00023009248
4,831	Randomizing, a Practical Method for Protecting Statistical Databases Against Compromise	1982	VLDB	6.3879325e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,067	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB
2	276	Towards Practical Differential Privacy for SQL Queries	2018	VLDB
3	1,991	Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy	2012	VLDB
4	9,783	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB
5	626	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS
6	1,530	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
7	12,598	The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases	2012	PODS
8	8,139	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB
9	3,993	Output Perturbation with Query Relaxation	2008	VLDB
10	122	Revealing Information while Preserving Privacy	2003	PODS