Locally private Jaccard similarity estimation

摘要

Jaccard Similarity has been widely used to measure the distance between two sets (or preferenceprofiles) owned by two different users. Yet, in the private data collection scenario, it requiresthe untrusted curator could only estimate an approximately accurate Jaccard similarity of theinvolved users but without being allowed to access their preference profiles. This paper aims toaddress the above requirements by considering the local differential privacy model. To achievethis, we initially focused on a particular hash technique, MinHash, which was originally inventedto estimate the Jaccard similarity efficiently.We designed the PrivMin algorithm to achieve theperturbation ofMinHash signature by adopting Exponentialmechanism and build the Locally DifferentiallyPrivate Jaccard Similarity Estimation (LDP-JSE) protocol for allowing the untrusted curatorto approximately estimate Jaccard similarity. Theoretical and empirical results demonstrate thatthe proposed protocol can retain a highly acceptable utility of the estimated similarity as well aspreserving privacy.