Locally private Jaccard similarity estimation

Yan, Z; Wu, Q; Ren, M; Liu, J; Liu, S; Qiu, S

Locally private Jaccard similarity estimation

Yan, Z Wu, Q Ren, M Liu, J Liu, S

Qiu, S

Permalink

Publication Type:: Journal Article
Citation:: Concurrency Computation, 2019, 31 (24)
Issue Date:: 2019-12-25

Closed Access

	Filename	Description	Size
	cpe.4889.pdf	Published Version	1.08 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Yan, Z	en_US
dc.contributor.author	Wu, Q	en_US
dc.contributor.author	Ren, M	en_US
dc.contributor.author	Liu, J	en_US
dc.contributor.author	Liu, S https://orcid.org/0000-0001-6062-6580	en_US
dc.contributor.author	Qiu, S	en_US
dc.date.accessioned	2020-04-15T06:43:55Z
dc.date.available	2020-04-15T06:43:55Z
dc.date.issued	2019-12-25	en_US
dc.identifier.citation	Concurrency Computation, 2019, 31 (24)	en_US
dc.identifier.issn	1532-0626	en_US
dc.identifier.uri	http://hdl.handle.net/10453/140005
dc.description.abstract	© 2018 John Wiley & Sons, Ltd. Jaccard Similarity has been widely used to measure the distance between two sets (or preference profiles) owned by two different users. Yet, in the private data collection scenario, it requires the untrusted curator could only estimate an approximately accurate Jaccard similarity of the involved users but without being allowed to access their preference profiles. This paper aims to address the above requirements by considering the local differential privacy model. To achieve this, we initially focused on a particular hash technique, MinHash, which was originally invented to estimate the Jaccard similarity efficiently. We designed the PrivMin algorithm to achieve the perturbation of MinHash signature by adopting Exponential mechanism and build the Locally Differentially Private Jaccard Similarity Estimation (LDP-JSE) protocol for allowing the untrusted curator to approximately estimate Jaccard similarity. Theoretical and empirical results demonstrate that the proposed protocol can retain a highly acceptable utility of the estimated similarity as well as preserving privacy.	en_US
dc.relation.ispartof	Concurrency Computation	en_US
dc.relation.isbasedon	10.1002/cpe.4889	en_US
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Distributed Computing	en_US
dc.title	Locally private Jaccard similarity estimation	en_US
dc.type	Journal Article
utslib.citation.volume	24	en_US
utslib.citation.volume	31	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
utslib.for	0803 Computer Software	en_US
utslib.for	0805 Distributed Computing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - AAI - Advanced Analytics Institute Research Centre
utslib.copyright.status	closed_access	*
pubs.issue	24	en_US
pubs.publication-status	Published	en_US
pubs.volume	31	en_US

Abstract:

© 2018 John Wiley & Sons, Ltd. Jaccard Similarity has been widely used to measure the distance between two sets (or preference profiles) owned by two different users. Yet, in the private data collection scenario, it requires the untrusted curator could only estimate an approximately accurate Jaccard similarity of the involved users but without being allowed to access their preference profiles. This paper aims to address the above requirements by considering the local differential privacy model. To achieve this, we initially focused on a particular hash technique, MinHash, which was originally invented to estimate the Jaccard similarity efficiently. We designed the PrivMin algorithm to achieve the perturbation of MinHash signature by adopting Exponential mechanism and build the Locally Differentially Private Jaccard Similarity Estimation (LDP-JSE) protocol for allowing the untrusted curator to approximately estimate Jaccard similarity. Theoretical and empirical results demonstrate that the proposed protocol can retain a highly acceptable utility of the estimated similarity as well as preserving privacy.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/140005