Differentially Private Hierarchical Heavy Hitters
摘要
The task of finding _Hierarchical_ Heavy Hitters (HHH) was introduced by Cormode et al. [VLDB 2003] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we study differentially private HHH release in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the residual count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Meanwhile, in the streaming setting, although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the steaming setting is independent of the available space.
正文
The task of finding _Hierarchical_ Heavy Hitters (HHH) was introduced by Cormode et al. [VLDB 2003] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we study differentially private HHH release in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the residual count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Meanwhile, in the streaming setting, although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the steaming setting is independent of the available space. Authors: Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, Zhengyi Zhou Categories: cs.CR, cs.DS PDF: https://arxiv.org/pdf/2606.13563v1 Comment: This is the updated version of the PODS 2025 conference version. Note that the conference version has a bug in the privacy proof fro the non-streaming version. We have addressed the bug in this full version
标签
- category:cs.cr
- category:cs.ds
- primary_category:cs.cr
- source:arxiv
- type:paper
扩展字段
{
"arxiv_id": "2606.13563v1",
"authors": [
"Ari Biswas",
"Graham Cormode",
"Yaron Kanza",
"Divesh Srivastava",
"Zhengyi Zhou"
],
"categories": [
"cs.CR",
"cs.DS"
],
"comment": "This is the updated version of the PODS 2025 conference version. Note that the conference version has a bug in the privacy proof fro the non-streaming version. We have addressed the bug in this full version",
"doi": null,
"entry_id": "https://arxiv.org/abs/2606.13563v1",
"pdf_url": "https://arxiv.org/pdf/2606.13563v1",
"primary_category": "cs.CR",
"search_query": "cat:cs.CR",
"updated_at": "2026-06-11T16:48:35+00:00"
}