  The Sparse Vector Technique (SVT) is a fundamental technique for satisfying
differential privacy and has the unique quality that one can output some query
answers without apparently paying any privacy cost. SVT has been used in both
the interactive setting, where one tries to answer a sequence of queries that
are not known ahead of the time, and in the non-interactive setting, where all
queries are known. Because of the potential savings on privacy budget, many
variants for SVT have been proposed and employed in privacy-preserving data
mining and publishing. However, most variants of SVT are actually not private.
In this paper, we analyze these errors and identify the misunderstandings that
likely contribute to them. We also propose a new version of SVT that provides
better utility, and introduce an effective technique to improve the performance
of SVT. These enhancements can be applied to improve utility in the interactive
setting. Through both analytical and experimental comparisons, we show that, in
the non-interactive setting (but not the interactive setting), the SVT
technique is unnecessary, as it can be replaced by the Exponential Mechanism
(EM) with better accuracy.
