Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy
Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy
复制标题
DOI：
10.1145/2976749.2978409
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
Zhan Qin;Y. Yang;Ting Yu;Issa M. Khalil;Xiaokui Xiao;K. Ren
中科院分区：
文献类型：
--
作者：
Zhan Qin;Y. Yang;Ting Yu;Issa M. Khalil;Xiaokui Xiao;K. Ren
在本地差分隐私（LDP）中，每个用户在将噪声数据发送到数据收集器之前在本地扰动她的数据。然后后者分析数据以获得有用的统计数据。与集中式差分隐私的设置不同，在LDP中，数据收集器永远无法访问敏感数据的确切值，这不仅保护了数据贡献者的隐私，还保护了收集器本身免受潜在数据泄漏的风险。文献中现有的LDP解决方案大多局限于每个用户拥有一个数字或分类值的元组的情况，数据收集器计算基本的统计数据，如计数或平均值。据我们所知，没有现有的工作解决更复杂的数据挖掘任务，如沉重的打击发现集值数据。本文系统地研究了LDP下的重命中挖掘问题。我们首先回顾现有的解决方案，将它们扩展到重量级的估计，并解释为什么它们的有效性是有限的。然后，我们提出了LDPMiner，一个两阶段的机制，获得准确的重量级人物与LDP。其主要思想是首先使用隐私预算的一部分收集候选的重量级人物集，并将剩余的预算集中在第二阶段中细化候选集，这比直接从整个数据集获得重量级人物要有效得多。我们提供了深入的理论分析和广泛的实验来比较LDPMiner与以前解决方案的适应性。结果表明，LDPMiner显着改善了现有的方法。更重要的是，LDPMiner在实际环境中成功识别了大多数真正的重量级人物。
In local differential privacy (LDP), each user perturbs her data locally before sending the noisy data to a data collector. The latter then analyzes the data to obtain useful statistics. Unlike the setting of centralized differential privacy, in LDP the data collector never gains access to the exact values of sensitive data, which protects not only the privacy of data contributors but also the collector itself against the risk of potential data leakage. Existing LDP solutions in the literature are mostly limited to the case that each user possesses a tuple of numeric or categorical values, and the data collector computes basic statistics such as counts or mean values. To the best of our knowledge, no existing work tackles more complex data mining tasks such as heavy hitter discovery over set-valued data. In this paper, we present a systematic study of heavy hitter mining under LDP. We first review existing solutions, extend them to the heavy hitter estimation, and explain why their effectiveness is limited. We then propose LDPMiner, a two-phase mechanism for obtaining accurate heavy hitters with LDP. The main idea is to first gather a candidate set of heavy hitters using a portion of the privacy budget, and focus the remaining budget on refining the candidate set in a second phase, which is much more efficient budget-wise than obtaining the heavy hitters directly from the whole dataset. We provide both in-depth theoretical analysis and extensive experiments to compare LDPMiner against adaptations of previous solutions. The results show that LDPMiner significantly improves over existing methods. More importantly, LDPMiner successfully identifies the majority true heavy hitters in practical settings.