Proceedings of the 2022 International Conference on Management of Data · 2022 · 40 citations · 32 references
ComputingComputer ScienceAlgorithmsCryptographyDatabasesData AnonymizationDatabase PrivacyDifferential PrivacyQuery OptimizationQuery ProcessingStructured Query LanguageConstraintsPrivacy-preserving Query ProcessingPrivacy-preserving QueryingPrivate Query AnsweringPrivate Query ProcessingQuery Answering Under Privacy ConstraintsQuery Privacy
Answering SPJA queries under differential privacy (DP), including graph pattern counting under node-DP as an important special case, has received considerable attention in recent years. The dual challenge of foreign-key constraints and self-joins is particularly tricky to deal with, and no existing DP mechanisms can correctly handle both. For the special case of graph pattern counting under node-DP, the existing mechanisms are correct (i.e., satisfy DP), but they do not offer nontrivial utility guarantees or are very complicated and costly. In this paper, we propose the first DP mechanism for answering arbitrary SPJA queries in a database with foreign-key constraints. Meanwhile, it achieves a fairly strong notion of optimality, which can be considered as a small and natural relaxation of instance optimality. Finally, our mechanism is simple enough that it can be easily implemented on top of any RDBMS and an LP solver. Experimental results show that it offers order-of-magnitude improvements in terms of utility over existing techniques, even those specifically designed for graph pattern counting.
32
Deep Learning with Differential Privacy
Martı́n Abadi, Andy Chu, Ian Goodfellow et al. · 2016 · 5.9K citations · Full text
{SNAP Datasets}: {Stanford} Large Network Dataset Collection
Jure Leskovec, Andrej Krevl · 2014 · 2.8K citations
Frank McSherry · 2009 · 1.1K citations
Smooth sensitivity and sampling in private data analysis
Kobbi Nissim, Sofya Raskhodnikova, Adam Smith · 2007 · 1K citations