推荐 3.5
Conf: 50%
本文提出并研究了在差分隐私保护下释放层次重击者(Hierarchical Heavy Hitters, HHH)的问题。层次重击者是经典重击者问题的推广,最早由Cormode等人在VLDB 2003中引入,用于在数据流中识别在层次结构上显著的项。尽管数据流中的HHH查找已被广泛研究,但在底层数据包含隐私信息时,如何安全地释放HHH结果尚未被探索。本文分别考察了非流式(静态数据集)和流式两种场景。在非流式设置中,作者发现了一个令人惊讶的结果:对于任何前缀,估计残差计数(residual count)的相对误差与层次的高度以及流中重击者的数量无关。这意味着即使在复杂的层次结构下,相对精度也能保持稳定。在流式设置中,虽然HHH的精确版本具有较低的全局灵敏度(因为计数查询是1-敏感的),但用于流式处理的近似函数却导致了较高的全局灵敏度,该灵敏度与可用空间呈线性关系。尽管如此,作者证明在流式设置中,估计频率的绝对误差与可用空间无关,从而突破了空间限制带来的障碍。本文的主要贡献包括:首次系统性地研究差分隐私HHH释放问题;在非流式场景中证明了一个与层次规模无关的误差界;在流式场景中给出了绝对误差独立于空间的证明。读者需要具备差分隐私、数据流算法以及层次重击者问题的基础知识。
💡 推荐理由: 层次重击者问题在许多应用(如网络监控、频次分析)中至关重要,但直接发布结果可能泄露用户隐私。本文首次在差分隐私框架下解决了这一难题,为隐私保护的数据发布提供了理论支撑,尤其适用于需要兼顾层次结构准确性和个人隐私的场景。
🎯 建议动作: 研究跟进
排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)