Document Open Access Logo

Approximate Range Counting Under Differential Privacy

Authors Ziyue Huang, Ke Yi

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.45.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Ziyue Huang
  • Hong Kong University of Science and Technology, Hong Kong, China
Ke Yi
  • Hong Kong University of Science and Technology, Hong Kong, China

Funding

This work has been supported by HKRGC under grants 16202317, 16201318, and 16201819.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.SoCG.2021.45

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Security and privacy → Formal methods and theory of security
Keywords
  • Differential Privacy
  • Approximate Range Counting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sunil Arya and David M Mount. Approximate range searching. In Proceedings of the eleventh annual symposium on Computational geometry, pages 172-181, 1995. Google Scholar
  2. Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891-923, 1998. Google Scholar
  3. Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 609-618, 2008. Google Scholar
  4. Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634-649. IEEE, 2015. Google Scholar
  5. TH Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In International Colloquium on Automata, Languages, and Programming, pages 405-417. Springer, 2010. Google Scholar
  6. Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. Differentially private spatial decompositions. In 2012 IEEE 28th International Conference on Data Engineering, pages 20-31. IEEE, 2012. Google Scholar
  7. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006. Google Scholar
  8. Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715-724, 2010. Google Scholar
  9. Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N Rothblum. Pure differential privacy for rectangle queries via private partitions. In International Conference on the Theory and Application of Cryptology and Information Security, pages 735-751. Springer, 2015. Google Scholar
  10. Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trendsregistered in Theoretical Computer Science, 9(3-4):211-407, 2014. Google Scholar
  11. Mehmet Emre Gursoy, Ali Inan, Mehmet Ercan Nergiz, and Yucel Saygin. Differentially private nearest neighbor classification. Data Mining and Knowledge Discovery, 31(5):1544-1575, 2017. Google Scholar
  12. Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In 2010 IEEE Annual Symposium on Foundations of Computer Science, pages 61-70. IEEE, 2010. Google Scholar
  13. Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705-714, 2010. Google Scholar
  14. Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially private histograms through consistency. Proceedings of the VLDB Endowment, 3(1-2):1021-1032, 2010. Google Scholar
  15. Ziyue Huang and Ke Yi. Approximate range counting under differential privacy. Available at URL: https://www.cse.ust.hk/~yike/DPRangeCount.pdf.
  16. Chao Li, Michael Hay, Gerome Miklau, and Yue Wang. A data-and workload-aware algorithm for range queries under differential privacy. Proceedings of the VLDB Endowment, 7(5):341-352, 2014. Google Scholar
  17. J. Matoušek. Geometric Discrepancy: An Illustrated Guide. Springer-Verlag, Berlin, 1999. Google Scholar
  18. Shanmugavelayutham Muthukrishnan and Aleksandar Nikolov. Optimal private halfspace counting via discrepancy. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1285-1292, 2012. Google Scholar
  19. Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 351-360, 2013. Google Scholar
  20. Wahbeh Qardaji, Weining Yang, and Ninghui Li. Differentially private grids for geospatial data. In 2013 IEEE 29th international conference on data engineering (ICDE), pages 757-768. IEEE, 2013. Google Scholar
  21. Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms. Proceedings of the VLDB Endowment, 6(14):1954-1965, 2013. Google Scholar
  22. Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347-450. Springer, 2017. Google Scholar
  23. Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. Differential privacy via wavelet transforms. IEEE Transactions on knowledge and data engineering, 23(8):1200-1214, 2010. Google Scholar
  24. Jun Zhang, Xiaokui Xiao, and Xing Xie. Privtree: A differentially private algorithm for hierarchical decompositions. In Proceedings of the 2016 International Conference on Management of Data, pages 155-170, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact