DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2021.45

Approximate Range Counting Under Differential Privacy

Authors: Ziyue Huang and Ke Yi

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

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.

Cite as

Ziyue Huang and Ke Yi. Approximate Range Counting Under Differential Privacy. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SoCG.2021.45},
  URN =		{urn:nbn:de:0030-drops-138441},
  doi =		{10.4230/LIPIcs.SoCG.2021.45},
  annote =	{Keywords: Differential Privacy, Approximate Range Counting}
}

Search Results

Documents authored by Huang, Ziyue

Approximate Range Counting Under Differential Privacy

Abstract

Cite as

Thanks for your feedback!

Could not send message