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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	International Conference on Similarity Search and Applications : SISAP 2020
Forlag	Springer
Publikationsdato	2020
Sider	18-32
DOI	https://doi.org/10.1007/978-3-030-60936-8_2
Status	Udgivet - 2020
Begivenhed	International Conference on Similarity Search and Applications - Reykjavik, Island Varighed: 1 okt. 2025 → 3 okt. 2025 Konferencens nummer: 18 https://www.sisap.org/2025

Konference

Konference	International Conference on Similarity Search and Applications
Nummer	18
Land/Område	Island
By	Reykjavik
Periode	01/10/2025 → 03/10/2025
Internetadresse	https://www.sisap.org/2025

Navn	Lecture Notest in Computer Science
Vol/bind	12440
ISSN	0302-9743

Emneord

Locally Differential Privacy
Jaccard Similarity
MinHash
Generalized Randomized Response
Laplace Mechanism

Adgang til dokumentet

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

2008.08134Andet version, 1,36 MB

Citationsformater

@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. i International Conference on Similarity Search and Applications: SISAP 2020. Springer, Lecture Notest in Computer Science, bind 12440, s. 18-32, International Conference on Similarity Search and Applications, Reykjavik, Island, 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. s. 18-32 (Lecture Notest in Computer Science, Bind 12440).

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater