Please use this identifier to cite or link to this item:
Title: Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
Authors: Yuan, Ganzhao
Zhang, Zhenjie
Winslett, Marianne
Xiao, Xiaokui
Yang, Yin
Hao, Zhifeng
Keywords: Linear counting query
Differential privacy
Issue Date: 2015
Source: Yuan, G., Zhang, Z., Winslett, M., Xiao, X., Yang, Y., & Hao, Z. (2015). Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy. ACM Transactions on Database Systems, 40(2), 11-.
Series/Report no.: ACM Transactions on Database Systems
Abstract: Differential privacy is a promising privacy-preserving paradigm for statistical query processing over sensitive data. It works by injecting random noise into each query result such that it is provably hard for the adversary to infer the presence or absence of any individual record from the published noisy results. The main objective in differentially private query processing is to maximize the accuracy of the query results while satisfying the privacy guarantees. Previous work, notably Li et al. [2010], has suggested that, with an appropriate strategy, processing a batch of correlated queries as a whole achieves considerably higher accuracy than answering them individually. However, to our knowledge there is currently no practical solution to find such a strategy for an arbitrary query batch; existing methods either return strategies of poor quality (often worse than naive methods) or require prohibitively expensive computations for even moderately large domains. Motivated by this, we propose a low-rank mechanism (LRM), the first practical differentially private technique for answering batch linear queries with high accuracy. LRM works for both exact (i.e., ε-) and approximate (i.e., (ε, δ)-) differential privacy definitions. We derive the utility guarantees of LRM and provide guidance on how to set the privacy parameters, given the user's utility expectation. Extensive experiments using real data demonstrate that our proposed method consistently outperforms state-of-the-art query processing solutions under differential privacy, by large margins.
ISSN: 0362-5915
DOI: 10.1145/2699501
Schools: School of Computer Science and Engineering 
Rights: © 2015 ACM. This is the author created version of a work that has been peer reviewed and accepted for publication by ACM Transactions on Database Systems, ACM. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy.pdf793.39 kBAdobe PDFThumbnail

Citations 20

Updated on Feb 24, 2024

Web of ScienceTM
Citations 20

Updated on Oct 31, 2023

Page view(s) 50

Updated on Feb 27, 2024

Download(s) 50

Updated on Feb 27, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.