{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:28Z","timestamp":1778807848155,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>\n            The task of finding\n            <jats:italic toggle=\"yes\">Hierarchical<\/jats:italic>\n            Heavy Hitters (HHH) was introduced by Cormode et al. [12] 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 formalise and study the notion of differentially private HHH, 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 count for any prefix is\n            <jats:italic toggle=\"yes\">independent<\/jats:italic>\n            of the height of the hierarchy and the number of heavy hitters in the stream. Additionally, our algorithms also improve the error guarantees of Ghazi et al. [24] for the problem of counting over trees. Meanwhile, in the streaming setting, the main issue is that 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 streaming setting is independent of the available space.\n          <\/jats:p>","DOI":"10.1145\/3695826","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-25","source":"Crossref","is-referenced-by-count":7,"title":["Differentially Private Hierarchical Heavy Hitters"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6412-844X","authenticated-orcid":false,"given":"Ari","family":"Biswas","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0698-0922","authenticated-orcid":false,"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"University of Warwick and Meta, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6056-595X","authenticated-orcid":false,"given":"Yaron","family":"Kanza","sequence":"additional","affiliation":[{"name":"AT&amp;T Chief Data Office, Bedminster, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7609-9217","authenticated-orcid":false,"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Chief Data Office, Bedminster, New Jersey, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-2866-4746","authenticated-orcid":false,"given":"Zhengyi","family":"Zhou","sequence":"additional","affiliation":[{"name":"AT&amp;T Chief Data Office, Bedminster, New Jersey, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_2_1","volume-title":"Differential privacy on finite computers. arXiv preprint arXiv:1709.05396","author":"Balcer Victor","year":"2017","unstructured":"Victor Balcer and Salil Vadhan. 2017. Differential privacy on finite computers. arXiv preprint arXiv:1709.05396 (2017)."},{"key":"e_1_2_1_3_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Bassily Raef","year":"2017","unstructured":"Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Guha Thakurta. 2017. Practical locally private heavy hitters. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_2_1_4_1","first-page":"18","article-title":"Bounds for Frequency Estimation of Packet Streams","volume":"10","author":"Bose Prosenjit","year":"2003","unstructured":"Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang. 2003. Bounds for Frequency Estimation of Packet Streams.. In SIROCCO, Vol. 10. 18--20.","journal-title":"SIROCCO"},{"key":"e_1_2_1_5_1","first-page":"1","article-title":"Simultaneous private learning of multiple concepts","volume":"20","author":"Bun Mark","year":"2019","unstructured":"Mark Bun, Kobbi Nissim, and Uri Stemmer. 2019. Simultaneous private learning of multiple concepts. Journal of Machine Learning Research, Vol. 20, 94 (2019), 1--34.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.85"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--14162--1_34"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31680-7_8"},{"key":"e_1_2_1_10_1","volume-title":"On the privacy properties of variants on the sparse vector technique. arXiv preprint arXiv:1508.07306","author":"Chen Yan","year":"2015","unstructured":"Yan Chen and Ashwin Machanavajjhala. 2015. On the privacy properties of variants on the sparse vector technique. arXiv preprint arXiv:1508.07306 (2015)."},{"key":"e_1_2_1_11_1","volume-title":"Differential privacy in the shuffle model: A survey of separations. arXiv preprint arXiv:2107.11839","author":"Cheu Albert","year":"2021","unstructured":"Albert Cheu. 2021. Differential privacy in the shuffle model: A survey of separations. arXiv preprint arXiv:2107.11839 (2021)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50048-3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007588"},{"key":"e_1_2_1_14_1","volume-title":"Finding hierarchical heavy hitters in streaming data. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Cormode Graham","year":"2008","unstructured":"Graham Cormode, Flip Korn, S Muthukrishnan, and Divesh Srivastava. 2008. Finding hierarchical heavy hitters in streaming data. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 1, 4 (2008), 1--48."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274608"},{"key":"e_1_2_1_16_1","volume-title":"14th USENIX symposium on networked systems design and implementation (NSDI 17)","author":"Corrigan-Gibbs Henry","year":"2017","unstructured":"Henry Corrigan-Gibbs and Dan Boneh. 2017. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (NSDI 17). 259--282."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589268"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746580"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250804"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536467"},{"key":"e_1_2_1_21_1","volume-title":"Foundations and Trends\u00ae in Theoretical Computer Science","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, Vol. 9, 3--4 (2014), 211--407."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384297"},{"key":"e_1_2_1_24_1","volume-title":"On Differentially Private Counting on Trees. arXiv preprint arXiv:2212.11967","author":"Ghazi Badih","year":"2022","unstructured":"Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. 2022. On Differentially Private Counting on Trees. arXiv preprint arXiv:2212.11967 (2022)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536464"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065211"},{"key":"e_1_2_1_28_1","volume-title":"International conference on machine learning. PMLR, 1376--1385","author":"Kairouz Peter","year":"2015","unstructured":"Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. In International conference on machine learning. PMLR, 1376--1385."},{"key":"e_1_2_1_29_1","volume-title":"Conference on Learning Theory. PMLR, 2747--2776","author":"Kaplan Haim","year":"2021","unstructured":"Haim Kaplan, Yishay Mansour, and Uri Stemmer. 2021. The sparse vector technique, revisited. In Conference on Learning Theory. PMLR, 2747--2776."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526733"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588673"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11023-020-09529-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73871-8_17"},{"key":"e_1_2_1_34_1","volume-title":"Understanding the sparse vector technique for differential privacy. arXiv preprint arXiv:1603.01699","author":"Lyu Min","year":"2016","unstructured":"Min Lyu, Dong Su, and Ninghui Li. 2016. Understanding the sparse vector technique for differential privacy. arXiv preprint arXiv:1603.01699 (2016)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972924.16"},{"key":"e_1_2_1_37_1","volume-title":"Theory of Cryptography Conference. Springer, 157--175","author":"Murtagh Jack","year":"2015","unstructured":"Jack Murtagh and Salil Vadhan. 2015. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference. Springer, 157--175."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902296"},{"key":"e_1_2_1_39_1","unstructured":"David Pujol and Damien Desfontaines. 2023. Open problem - Better privacy guarantees for larger groups. DifferentialPrivacy.org. https:\/\/differentialprivacy.org\/open-problem-better-privacy-guarantees-for-larger-groups\/."},{"key":"e_1_2_1_40_1","volume-title":"Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00597","author":"Steinke Thomas","year":"2022","unstructured":"Thomas Steinke. 2022. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00597 (2022)."},{"key":"e_1_2_1_41_1","volume-title":"Between pure and approximate differential privacy. arXiv preprint arXiv:1501.06095","author":"Steinke Thomas","year":"2015","unstructured":"Thomas Steinke and Jonathan Ullman. 2015. Between pure and approximate differential privacy. arXiv preprint arXiv:1501.06095 (2015)."},{"key":"e_1_2_1_42_1","volume-title":"Conference on Learning Theory. PMLR, 819--850","author":"Thakurta Abhradeep Guha","year":"2013","unstructured":"Abhradeep Guha Thakurta and Adam Smith. 2013. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory. PMLR, 819--850."},{"key":"e_1_2_1_43_1","first-page":"12691","article-title":"Differentially private linear sketches: Efficient implementations and applications","volume":"35","author":"Zhao Fuheng","year":"2022","unstructured":"Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. 2022. Differentially private linear sketches: Efficient implementations and applications. Advances in Neural Information Processing Systems, Vol. 35 (2022), 12691--12704.","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695826","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695826","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:32:35Z","timestamp":1755916355000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695826"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695826"],"URL":"https:\/\/doi.org\/10.1145\/3695826","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}