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. ISSN 2150-8097. doi:10.14778/3339490.3339496

Preview

PDF WRAP-answering-range-queries-local-differential-privacy-Cormode-2019.pdf - Accepted Version - Requires a PDF viewer. Download (827Kb) | Preview

Request Changes to record.

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 > 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:	Date Event 2019 Published 25 June 2019 Accepted
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
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID ERC-2014-CoG 647557 H2020 European Research Council http://dx.doi.org/10.13039/100010663 EPSRC grant EP/N510129/1 Alan Turing Institute http://dx.doi.org/10.13039/100012338 UNSPECIFIED AT and T http://dx.doi.org/10.13039/100004347
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:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads