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.5077101e-05
Overall Rank: 7,501 | 49.57%
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,412	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.6112155e-05
8,133	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	5.3931029e-05
8,592	Differentially Private Hierarchical Count-of-Counts Histograms	2018	VLDB	5.3069959e-05
9,745	Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms	2020	VLDB	5.1349531e-05
13,845	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.00031089378
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
558	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016470707
1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010349919
2,298	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.6731734e-05
3,938	DPT: Differentially Private Trajectory Synthesis Using Hierarchical Reference Systems	2015	VLDB	6.9153613e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
2	13,099	Privacy in Data Systems	2003	PODS
3	11,090	Private Synthetic Data Generation in Bounded Memory	2025	PODS
4	3,123	Bayesian Differential Privacy on Correlated Data	2015	SIGMOD
5	1,166	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB
6	10,539	A General Framework for Per-record Differential Privacy	2026	SIGMOD
7	2,090	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB
8	1,155	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,845	DIAS: Differentially Private Interactive Algorithm Selection using Pythia	2017	SIGMOD