Differentially Private Range Counting in Planar Graphs for Spatial Sensing

Abhirup Ghosh, Jiaxin Ding, Rik Sarkar, Jie Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper considers the problem of privately reporting counts of events recorded by devices in different regions of the plane. Unlike previous range query methods, our approach is not limited to rectangular ranges. We devise novel hierarchical data structures to answer queries over arbitrary planar graphs. This construction relies on balanced planar separators to represent shortest paths using O(log n) number of canonical paths, where n is the number of nodes in the graph. Pre-computed sums along these canonical paths allow efficient computations of 1D counting range queries along any shortest path. We make use of differential forms together with the 1D mechanism to answer 2D queries in which a range is a union of faces in the planar graph. The methods are designed such that the range queries could be answered with differential privacy guarantee on any single event, with only a poly-logarithmic error. They also allow private range queries to be performed in a distributed setup. Theoretical and experimental results confirm that the methods are efficient and accurate on real data and incur less error than competing existing methods.
Original languageEnglish
Title of host publicationIEEE INFOCOM 2020 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages2233-2242
Number of pages10
ISBN (Electronic)978-1-7281-6412-0
ISBN (Print)978-1-7281-6413-7
DOIs
Publication statusPublished - 4 Aug 2020
EventIEEE International Conference on Computer Communications - Virtual Conference, Canada
Duration: 6 Jul 20209 Jul 2020
https://infocom2020.ieee-infocom.org/

Publication series

Name
PublisherIEEE
ISSN (Print)0743-166X
ISSN (Electronic)2641-9874

Conference

ConferenceIEEE International Conference on Computer Communications
Abbreviated titleINFOCOM 2020
Country/TerritoryCanada
CityVirtual Conference
Period6/07/209/07/20
Internet address

Keywords

  • range query
  • differential privacy
  • planar graphs
  • Internet of Things

Fingerprint

Dive into the research topics of 'Differentially Private Range Counting in Planar Graphs for Spatial Sensing'. Together they form a unique fingerprint.

Cite this