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

Abstract

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
PublisherSpringer
Publication date2020
Pages18-32
DOIs
Publication statusPublished - 2020
SeriesLecture Notest in Computer Science
Volume12440
ISSN0302-9743

Keywords

  • Locally Differential Privacy
  • Jaccard Similarity
  • MinHash
  • Generalized Randomized Response
  • Laplace Mechanism

Fingerprint

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

Cite this