Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory
Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory
复制标题
DOI：
10.1145/3639285
复制
发表时间：
2023-11
期刊：
影响因子：
--
通讯作者：
Xiaochen Li;Weiran Liu;Jian Lou;Yuan Hong;Lei Zhang;Zhan Qin;Kui Ren
中科院分区：
文献类型：
--
作者：
Xiaochen Li;Weiran Liu;Jian Lou;Yuan Hong;Lei Zhang;Zhan Qin;Kui Ren
Top-k频繁项检测是数据流挖掘中的一项基本任务。提出了许多有前途的解决方案，以提高内存效率，同时仍然保持高精度的检测Top-k项目。尽管存在内存效率问题，但如果用户在没有适当保护的情况下参与任务，则可能会遭受隐私损失，因为他们贡献的本地数据流可能会不断泄漏敏感的个人信息。然而，大多数现有的作品只专注于解决内存效率问题或隐私问题，但很少联合，这不能实现一个令人满意的折衷之间的内存效率，隐私保护和检测精度。在本文中，我们提出了一种新的框架HG-LDP实现精确的Top-k项目检测有限的内存开销，同时提供严格的局部差分隐私（LDP）保护。具体来说，我们确定了两个关键的挑战，自然产生的任务，这表明，直接应用现有的LDP技术将导致一个低劣的“准确性，隐私，内存效率”的权衡。因此，我们通过设计新颖的LDP随机化方法，解决了项目域的大尺寸和内存空间有限所造成的障碍，在框架下实例化了三个先进的计划。我们在合成数据集和真实数据集上进行了全面的实验，结果表明，所提出的高级方案实现了上级的“准确性-隐私性-内存效率”权衡，当项目域大小为41，270时，与基线方法相比节省了2300倍的内存。我们的代码通过链接匿名开源。
Top-k frequent items detection is a fundamental task in data stream mining. Many promising solutions are proposed to improve memory efficiency while still maintaining high accuracy for detecting the Top-k items. Despite the memory efficiency concern, the users could suffer from privacy loss if participating in the task without proper protection, since their contributed local data streams may continually leak sensitive individual information. However, most existing works solely focus on addressing either the memory-efficiency problem or the privacy concerns but seldom jointly, which cannot achieve a satisfactory tradeoff between memory efficiency, privacy protection, and detection accuracy. In this paper, we present a novel framework HG-LDP to achieve accurate Top-k item detection at bounded memory expense, while providing rigorous local differential privacy (LDP) protection. Specifically, we identify two key challenges naturally arising in the task, which reveal that directly applying existing LDP techniques will lead to an inferior "accuracy-privacy-memory efficiency" tradeoff. Therefore, we instantiate three advanced schemes under the framework by designing novel LDP randomization methods, which address the hurdles caused by the large size of the item domain and by the limited space of the memory. We conduct comprehensive experiments on both synthetic and real-world datasets to show that the proposed advanced schemes achieve a superior "accuracy-privacy-memory efficiency" tradeoff, saving 2300× memory over baseline methods when the item domain size is 41,270. Our code is anonymously open-sourced via the link.