Skip to main content

Free gap information from the differentially private sparse vector and noisy max mechanisms

Publication ,  Conference
Ding, Z; Wang, Y; Zhang, D; Kifer, D
Published in: Proceedings of the VLDB Endowment
January 1, 2020

Noisy Max and Sparse Vector are selection algorithms for differential privacy and serve as building blocks for more complex algorithms. In this paper we show that both algorithms can release additional information for free (i.e., at no additional privacy cost). Noisy Max is used to return the approximate maximizer among a set of queries. We show that it can also release for free the noisy gap between the approximate maximizer and runner-up. This free information can improve the accuracy of certain subsequent counting queries by up to 50%. Sparse Vector is used to return a set of queries that are approximately larger than a fixed threshold. We show that it can adaptively control its privacy budget (use less budget for queries that are likely to be much larger than the threshold) in order to increase the amount of queries it can process. These results follow from a careful privacy analysis.

Duke Scholars

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2020

Volume

13

Issue

3

Start / End Page

293 / 306

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Ding, Z., Wang, Y., Zhang, D., & Kifer, D. (2020). Free gap information from the differentially private sparse vector and noisy max mechanisms. In Proceedings of the VLDB Endowment (Vol. 13, pp. 293–306). https://doi.org/10.14778/3368289.3368295
Ding, Z., Y. Wang, D. Zhang, and D. Kifer. “Free gap information from the differentially private sparse vector and noisy max mechanisms.” In Proceedings of the VLDB Endowment, 13:293–306, 2020. https://doi.org/10.14778/3368289.3368295.
Ding Z, Wang Y, Zhang D, Kifer D. Free gap information from the differentially private sparse vector and noisy max mechanisms. In: Proceedings of the VLDB Endowment. 2020. p. 293–306.
Ding, Z., et al. “Free gap information from the differentially private sparse vector and noisy max mechanisms.” Proceedings of the VLDB Endowment, vol. 13, no. 3, 2020, pp. 293–306. Scopus, doi:10.14778/3368289.3368295.
Ding Z, Wang Y, Zhang D, Kifer D. Free gap information from the differentially private sparse vector and noisy max mechanisms. Proceedings of the VLDB Endowment. 2020. p. 293–306.

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2020

Volume

13

Issue

3

Start / End Page

293 / 306

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics