License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.45
URN: urn:nbn:de:0030-drops-138441
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13844/
Go to the corresponding LIPIcs Volume Portal

Huang, Ziyue ; Yi, Ke

Approximate Range Counting Under Differential Privacy

pdf-format:
LIPIcs-SoCG-2021-45.pdf (0.8 MB)

Abstract

Range counting under differential privacy has been studied extensively. Unfortunately, lower bounds based on discrepancy theory suggest that large errors have to be introduced in order to preserve privacy: Essentially for any range space (except axis-parallel rectangles), the error has to be polynomial. In this paper, we show that by allowing a standard notion of geometric approximation where points near the boundary of the range may or may not be counted, the error can be reduced to logarithmic. Furthermore, our approximate range counting data structure can be used to solve the approximate nearest neighbor (ANN) problem and k-NN classification, leading to the first differentially private algorithms for these two problems with provable guarantees on the utility.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs.SoCG.2021.45,
  author =	{Huang, Ziyue and Yi, Ke},
  title =	{{Approximate Range Counting Under Differential Privacy}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13844},
  URN =		{urn:nbn:de:0030-drops-138441},
  doi =		{10.4230/LIPIcs.SoCG.2021.45},
  annote =	{Keywords: Differential Privacy, Approximate Range Counting}
}

Keywords: Differential Privacy, Approximate Range Counting
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI