Differentially Private Sketches for Jaccard Similarity Estimation
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. The paper ends with a critical discussion of related work.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Private Sketches for Linear Regression
Linear regression is frequently applied in a variety of domains, some of which might contain sensitive information. This necessitates that the application of these methods does not reveal private information. Differentia…
Computational EfficiencyPrivate and Communication-Efficient Federated Learning based on Differentially Private Sketches
Federated learning (FL) faces two primary challenges: the risk of privacy leakage due to parameter sharing and communication inefficiencies. To address these challenges, we propose DPSFL, a federated learning method that…
Federated LearningDecision Tree for Locally Private Estimation with Public Data
We propose conducting locally differentially private (LDP) estimation with the aid of a small amount of public data to enhance the performance of private estimation. Specifically, we introduce an efficient algorithm call…
Sampling-Based Estimation of Jaccard Containment and Similarity
This paper addresses the problem of estimating the containment and similarity between two sets using only random samples from each set, without relying on sketches of full sets. The study introduces a binomial model for …
Distributed Differentially Private Data Analytics via Secure Sketching
We introduce the linear-transformation model, a distributed model of differentially private data analysis. Clients have access to a trusted platform capable of applying a public matrix to their inputs. Such computations …
Computational Efficiency