Locally private Jaccard similarity estimation. (27th September 2018)

• Record Type: Journal Article
• Authors: Yan, Ziqi; Wu, Qiong; Ren, Meng; Liu, Jiqiang; Liu, Shaowu; Qiu, Shuo
• Other Names: Li Gang guestEditor.; Batten Lynn guestEditor.; Foschini Luca guestEditor.; Kim Hyunbum guestEditor.; Dong Fang guestEditor.; Wu Chenshu guestEditor.; Gao Shangce guestEditor.
• Is Part Of: Concurrency and computation. Volume 31:Number 24(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-09-27
• Subjects: Jaccard similarity -- local differential privacy -- MinHash; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4889
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: 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.