Differentially Private Sketches for Jaccard Similarity Estimation

Martin Aumüller, Bourgeat, Schmurr

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

This paper describes two locally-differential private algorithms for releasing user vectors such that the Jaccard similarity between these vectors can be efficiently estimated. The basic building block is the well known MinHash method. To achieve a privacy-utility trade-off, MinHash is extended in two ways using variants of Generalized Randomized Response and the Laplace Mechanism. A theoretical analysis provides bounds on the absolute error and experiments show the utility-privacy trade-off on synthetic and real-world data. A full version of this paper is available at http://arxiv.org/abs/2008.08134.
OriginalsprogEngelsk
TitelInternational Conference on Similarity Search and Applications : SISAP 2020
ForlagSpringer
Publikationsdato2020
Sider18-32
DOI
StatusUdgivet - 2020
NavnLecture Notest in Computer Science
Vol/bind12440
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Differentially Private Sketches for Jaccard Similarity Estimation'. Sammen danner de et unikt fingeraftryk.

Citationsformater