论文标题
Jaccard相似性估计的差异私有草图
Differentially Private Sketches for Jaccard Similarity Estimation
论文作者
论文摘要
本文介绍了两种局部差异的私人算法，用于释放用户向量，从而可以有效地估计这些向量之间的jaccard相似性。基本的构建块是众所周知的Minhash方法。为了实现隐私性权衡取舍，使用广义随机响应和拉普拉斯机制的变体以两种方式扩展了Minhash。理论分析提供了绝对误差的界限，实验显示了综合和现实世界数据的公用事业私人关系权衡。本文以对相关工作的批判性讨论结尾。
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.
