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


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(logn) 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 (US)
Title of host publicationINFOCOM 2020 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781728164120
StatePublished - Jul 2020
Externally publishedYes
Event38th IEEE Conference on Computer Communications, INFOCOM 2020 - Toronto, Canada
Duration: Jul 6 2020Jul 9 2020

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Conference38th IEEE Conference on Computer Communications, INFOCOM 2020

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


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


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

Cite this