Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Answering range queries under local differential privacy

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

[img]
Preview
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

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:
DateEvent
2019Published
25 June 2019Accepted
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 IDRIOXX Funder NameFunder ID
ERC-2014-CoG 647557H2020 European Research Councilhttp://dx.doi.org/10.13039/100010663
EPSRC grant EP/N510129/1Alan Turing Institutehttp://dx.doi.org/10.13039/100012338
UNSPECIFIEDAT and Thttp://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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us