Pythia: Data Dependent Differentially Private Algorithm Selection

Summary: Pythia, a data-dependent meta-algorithm, learns data properties to pick the best DP algorithm. End-to-end DP system that tests low-sensitivity properties and applies the chosen algorithm, improving histograms, 1- and 2-D range queries, and Naive Bayes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2774074a35d531af
Venue: SIGMOD
Year: 2017
Pagerank: 5.5051028e-05
Overall Rank: 7,506 | 49.56%
DOI: 10.1145/3035918.3035945

Incoming Non-self Citations Over Time

Authors

1. Ios Kotsogiannis (Duke University)
2. Ashwin Machanavajjhala (Duke University)
3. Michael Hay (Colgate University)
4. Gerome Miklau (University of Massachusetts Amherst)

BibTeX Citation

@inproceedings{kotsogiannis_sigmod17,
        title = {{Pythia: Data Dependent Differentially Private Algorithm Selection}},
        author = {Kotsogiannis, Ios and Machanavajjhala, Ashwin and Hay, Michael and Miklau, Gerome},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3035945},
        url = {https://dl.acm.org/doi/10.1145/3035918.3035945},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,414	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.6080858e-05
8,139	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	5.3905499e-05
8,599	Differentially Private Hierarchical Count-of-Counts Histograms	2018	VLDB	5.3045399e-05
9,750	Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms	2020	VLDB	5.1325223e-05
13,850	DIAS: Differentially Private Interactive Algorithm Selection using Pythia	2017	SIGMOD	-

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.0003107472
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022404363
558	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.0001646292
1,530	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010345019
2,301	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.6690677e-05
3,939	DPT: Differentially Private Trajectory Synthesis Using Hierarchical Reference Systems	2015	VLDB	6.9120876e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,530	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
2	13,105	Privacy in Data Systems	2003	PODS
3	11,099	Private Synthetic Data Generation in Bounded Memory	2025	PODS
4	3,125	Bayesian Differential Privacy on Correlated Data	2015	SIGMOD
5	1,168	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB
6	10,550	A General Framework for Per-record Differential Privacy	2026	SIGMOD
7	2,091	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB
8	1,156	PrivBayes: Private Data Release via Bayesian Networks	2014	SIGMOD
9	64	Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis	2009	SIGMOD
10	13,850	DIAS: Differentially Private Interactive Algorithm Selection using Pythia	2017	SIGMOD