Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access

Understand

Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy.

• An ideal solution would use space close to information-theoretical lower bounds, have an error distribution that depends optimally on the desired privacy level, and allow fast random access to entries in the vector.
• However, existing approaches have only achieved two of these three goals.
• In this paper we introduce the Approximate Laplace Projection (ALP) mechanism for approximating k-sparse vectors.