The Library
Answering range queries under local differential privacy
Tools
Cormode, Graham, Kulkarni, Tejas M. and Srivastava, D. (2019) Answering range queries under local differential privacy. In: International Conference on Very Large Data Bases (VLDB), California, 26-30 Aug 2019. Published in: Proceedings of the VLDB Endowment, 12 (10). pp. 1126-1138. doi:10.14778/3339490.3339496 ISSN 2150-8097.
|
PDF
WRAP-answering-range-queries-local-differential-privacy-Cormode-2019.pdf - Accepted Version - Requires a PDF viewer. Download (827Kb) | Preview |
Official URL: https://doi.org/10.14778/3339490.3339496
Abstract
Counting the fraction of a population having an input within a specified interval i.e. a range query, is a fundamental data analysis primitive. Range queries can also be used to compute other core statistics such as quantiles, and to build prediction models. However,
frequently the data is subject to privacy concerns when it is drawn
from individuals, and relates for example to their financial, health,
religious or political status. In this paper, we introduce and analyze
methods to support range queries under the local variant of differential privacy [23], an emerging standard for privacy-preserving
data analysis.
The local model requires that each user releases a noisy view of
her private data under a privacy guarantee. While many works address the problem of range queries in the trusted aggregator setting,
this problem has not been addressed specifically under untrusted
aggregation (local DP) model even though many primitives have
been developed recently for estimating a discrete distribution. We
describe and analyze two classes of approaches for range queries,
based on hierarchical histograms and the Haar wavelet transform.
We show that both have strong theoretical accuracy guarantees on
variance. In practice, both methods are fast and require minimal
computation and communication resources. Our experiments show
that the wavelet approach is most accurate in high privacy settings,
while the hierarchical approach dominates for weaker privacy requirements.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Differential equations, Privacy -- Mathematical models, Computer networks -- Security measures, Computer security | ||||||||||||
Journal or Publication Title: | Proceedings of the VLDB Endowment | ||||||||||||
Publisher: | ACM | ||||||||||||
ISSN: | 2150-8097 | ||||||||||||
Official Date: | 2019 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 12 | ||||||||||||
Number: | 10 | ||||||||||||
Page Range: | pp. 1126-1138 | ||||||||||||
DOI: | 10.14778/3339490.3339496 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 7 August 2019 | ||||||||||||
Date of first compliant Open Access: | 13 August 2019 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | International Conference on Very Large Data Bases (VLDB) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | California | ||||||||||||
Date(s) of Event: | 26-30 Aug 2019 | ||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year