Differentially Private Sketches for Jaccard Similarity Estimation

Martin Aumüller, Bourgeat, Schmurr

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationInternational Conference on Similarity Search and Applications : SISAP 2020
Publication date2020
Publication statusPublished - 2020
SeriesLecture Notest in Computer Science


Dive into the research topics of 'Differentially Private Sketches for Jaccard Similarity Estimation'. Together they form a unique fingerprint.

Cite this