@article{Lebeda_Aumüller_Pagh_2022, title={Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access}, volume={12}, url={https://journalprivacyconfidentiality.org/index.php/jpc/article/view/809}, DOI={10.29012/jpc.809}, abstractNote={<div> <div>Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy.</div> <div>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.</div> <div>However, existing approaches have only achieved two of these three goals.</div> <div>&nbsp;</div> <div>In this paper we introduce the Approximate Laplace Projection (ALP) mechanism for approximating k-sparse vectors. This mechanism is shown to simultaneously have information-theoretically optimal space (up to constant factors), fast access to vector entries, and error of the same magnitude as the Laplace-mechanism applied to dense vectors.</div> <div>A key new technique is a <em>unary</em> representation of small integers, which we show to be robust against ’’randomized response’’ noise. This representation is combined with hashing, in the spirit of Bloom filters, to obtain a space-efficient, differentially private representation.</div> <br> <div>Our theoretical performance bounds are complemented by simulations which show that the constant factors on the main performance parameters are quite small, suggesting practicality of the technique.</div> </div>}, number={2}, journal={Journal of Privacy and Confidentiality}, author={Lebeda, Christian Janos and Aumüller, Martin and Pagh, Rasmus}, year={2022}, month={Nov.} }