Dual Query: Practical Private Query Release for High Dimensional Data - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Journal of Privacy and Confidentiality Année : 2016

Dual Query: Practical Private Query Release for High Dimensional Data

(1) , (2, 3) , (4) , (4) , (4)
1
2
3
4

Résumé

We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example , our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude.
Fichier non déposé

Dates et versions

hal-01702734 , version 1 (05-03-2018)

Identifiants

  • HAL Id : hal-01702734 , version 1

Citer

Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, Zhiwei Steven Wu. Dual Query: Practical Private Query Release for High Dimensional Data. Journal of Privacy and Confidentiality, 2016, 7 (Issue 2, Article N°4), pp.53 - 77. ⟨hal-01702734⟩
74 Consultations
1 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More