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: 5373
Venue: SIGMOD
Year: 2017
Pagerank: 5.6341162e-05
Overall Rank: 7,359 | 49.52%
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,361	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.7443476e-05
7,968	Optimizing Fitness-For-Use of Differentially Private Linear Queries	2021	VLDB	5.516666e-05
8,426	Differentially Private Hierarchical Count-of-Counts Histograms	2018	VLDB	5.4265571e-05
9,569	Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms	2020	VLDB	5.2528121e-05
13,532	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.00031639377
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
567	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016420715
1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010548904
2,300	Principled Evaluation of Differentially Private Algorithms using DPBench	2016	SIGMOD	8.7833594e-05
3,871	DPT: Differentially Private Trajectory Synthesis Using Hierarchical Reference Systems	2015	VLDB	7.0581665e-05

Semantically Similar Papers

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