Fetching the paper…

Reading the bibliography…

2015

On the Privacy Properties of Variants on the Sparse Vector Technique

Chen, Yan, Machanavajjhala, Ashwin

Original
PDF
Post on X

Understand

The sparse vector technique is a powerful differentially private primitive that allows an analyst to check whether queries in a stream are greater or lesser than a threshold.

This technique has a unique property -- the algorithm works by adding noise with a finite variance to the queries and the threshold, and guarantees privacy that only degrades with (a) the maximum sensitivity of any one query in stream, and (b) the number of positive answers output by the algorithm.
Recent work has developed variants of this algorithm, which we call {\em generalized private threshold testing}, and are claimed to have privacy guarantees that do not depend on the number of positive or negative answers output by the algorithm.
These algorithms result in a significant improvement in utility over the sparse vector technique for a given privacy budget, and have found applications in frequent itemset mining, feature selection in machine learning and generating synthetic data.

On the Privacy Properties of Variants on the Sparse Vector Technique · Around

Built on

Calibrating noise to sensitivity in private data analysis
C. Dwork, F. McSherry, K. Nissim, and A. Smith · 2006
Earlier work this paper cites.
United states department of health, human services. centers for disease control, and prevention. national center for health statistic. national home and hospice care survey, 2007
2007
Earlier work this paper cites.
Interactive privacy via the median mechanism
A. Roth and T. Roughgarden · 2010
Earlier work this paper cites.

Similar

Integrated public use microdata series: Version 5.0
K. S.Ruggles, J.Alexander and R.Goeken · 2010
Cited alongside, same era.
The algorithmic foundations of differential privacy
C. Dwork and A. Roth · 2013
Cited alongside, same era.
Uci machine learning repository
K.Bache and M.Lichman · 2013
Cited alongside, same era.

Then

Top-k frequent itemsets via differentially private fp-trees
J. Lee and C. W. Clifton · 2014
Later among the works it cites.
Differentially private algorithms for empirical machine learning
Original
B. Stoddard, Y. Chen, and A. Machanavajjhala · 2014
Later among the works it cites.
Differentially private high-dimensional data publication via sampling-based inference
R. Chen, Q. Xiao, Y. Zhang, and J. Xu · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…