Differentially Private Sketches for Jaccard Similarity Estimation

Martin Aumüller; Bourgeat; Schmurr

doi:10.1007/978-3-030-60936-8_2

Differentially Private Sketches for Jaccard Similarity Estimation

Martin Aumüller
, Bourgeat
, Schmurr

Algorithms

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-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 language	English
Title of host publication	International Conference on Similarity Search and Applications : SISAP 2020
Publisher	Springer
Publication date	2020
Pages	18-32
DOIs	https://doi.org/10.1007/978-3-030-60936-8_2
Publication status	Published - 2020
Event	International Conference on Similarity Search and Applications - Reykjavik, Iceland Duration: 1 Oct 2025 → 3 Oct 2025 Conference number: 18 https://www.sisap.org/2025

Conference

Conference	International Conference on Similarity Search and Applications
Number	18
Country/Territory	Iceland
City	Reykjavik
Period	01/10/2025 → 03/10/2025
Internet address	https://www.sisap.org/2025

Series	Lecture Notest in Computer Science
Volume	12440
ISSN	0302-9743

Keywords

Locally Differential Privacy
Jaccard Similarity
MinHash
Generalized Randomized Response
Laplace Mechanism

Access to Document

10.1007/978-3-030-60936-8_2

2008.08134Other version, 1.36 MB

Cite this

@inproceedings{e2040632f8d34a779c922aa37204aab7,

title = "Differentially Private Sketches for Jaccard Similarity Estimation",

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.",

keywords = "Locally Differential Privacy, Jaccard Similarity, MinHash, Generalized Randomized Response, Laplace Mechanism, Locally Differential Privacy, Jaccard Similarity, MinHash, Generalized Randomized Response, Laplace Mechanism",

author = "Martin Aum{\"u}ller and Bourgeat and Schmurr",

year = "2020",

doi = "10.1007/978-3-030-60936-8\_2",

language = "English",

series = "Lecture Notest in Computer Science",

publisher = "Springer",

pages = "18--32",

booktitle = "International Conference on Similarity Search and Applications",

address = "Germany",

note = "International Conference on Similarity Search and Applications, SISAP ; Conference date: 01-10-2025 Through 03-10-2025",

url = "https://www.sisap.org/2025",

}

Aumüller, M, Bourgeat & Schmurr 2020, Differentially Private Sketches for Jaccard Similarity Estimation. in International Conference on Similarity Search and Applications: SISAP 2020. Springer, Lecture Notest in Computer Science, vol. 12440, pp. 18-32, International Conference on Similarity Search and Applications, Reykjavik, Iceland, 01/10/2025. https://doi.org/10.1007/978-3-030-60936-8_2

Differentially Private Sketches for Jaccard Similarity Estimation. / Aumüller, Martin; Bourgeat; Schmurr.
International Conference on Similarity Search and Applications: SISAP 2020. Springer, 2020. p. 18-32 (Lecture Notest in Computer Science, Vol. 12440).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Differentially Private Sketches for Jaccard Similarity Estimation

AU - Aumüller, Martin

AU - Bourgeat,

AU - Schmurr,

N1 - Conference code: 18

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Locally Differential Privacy

KW - Jaccard Similarity

KW - MinHash

KW - Generalized Randomized Response

KW - Laplace Mechanism

KW - Locally Differential Privacy

KW - Jaccard Similarity

KW - MinHash

KW - Generalized Randomized Response

KW - Laplace Mechanism

U2 - 10.1007/978-3-030-60936-8_2

DO - 10.1007/978-3-030-60936-8_2

M3 - Article in proceedings

T3 - Lecture Notest in Computer Science

SP - 18

EP - 32

BT - International Conference on Similarity Search and Applications

PB - Springer

T2 - International Conference on Similarity Search and Applications

Y2 - 1 October 2025 through 3 October 2025

ER -

Differentially Private Sketches for Jaccard Similarity Estimation

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this