Differentially Private Hierarchical Heavy Hitters

Computer Science > Cryptography and Security [Submitted on 11 Jun 2026] Differentially Private Hierarchical Heavy Hitters Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, Zhengyi Zhou 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. Comments: 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 Subjects: Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2606.13563 [cs.CR]   (or arXiv:2606.13563v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.13563 Focus to learn more Submission history From: Ari Biswas [view email] [v1] Thu, 11 Jun 2026 16:48:35 UTC (1,377 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.DS References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)