{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:43Z","timestamp":1773482023098,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3588673","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"79-88","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9517-8466","authenticated-orcid":false,"given":"Christian Janos","family":"Lebeda","sequence":"first","affiliation":[{"name":"Basic Algorithms Research Copenhagen & IT University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2046-1627","authenticated-orcid":false,"given":"Jakub","family":"Tetek","sequence":"additional","affiliation":[{"name":"Basic Algorithms Research Copenhagen & University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_3_2_1_2_1","volume-title":"Differential Privacy Overview - Apple. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf Retrieved","year":"2023","unstructured":"Apple. [n.,d.]. Differential Privacy Overview - Apple. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf Retrieved April 13, 2023 from"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.809"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.679"},{"key":"e_1_3_2_1_5_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_3_2_1_6_1","unstructured":"Jeremiah Blocki Elena Grigorescu Tamalika Mukherjee and Samson Zhou. 2022. How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. arXiv preprint arXiv:2210.03831 (2022)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484557"},{"key":"e_1_3_2_1_8_1","volume-title":"Bounds for Frequency Estimation of Packet Streams. In SIROCCO 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, June 18--20","volume":"42","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 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, June 18--20, 2003, Ume\u00e5 Sweden (Proceedings in Informatics, Vol. 17), Jop F. Sibeyn (Ed.). Carleton Scientific, 33--42."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3344722"},{"key":"e_1_3_2_1_10_1","volume-title":"Conference on Uncertainty in Artificial Intelligence. PMLR, 1109--1118","author":"Carvalho Ricardo Silva","year":"2020","unstructured":"Ricardo Silva Carvalho, Ke Wang, Lovedeep Gondara, and Chunyan Miao. 2020. Differentially private top-k selection via stability on unknown domain. In Conference on Uncertainty in Artificial Intelligence. PMLR, 1109--1118."},{"key":"e_1_3_2_1_11_1","unstructured":"T.-H. Hubert Chan Mingfei Li Elaine Shi and Wenchang Xu. 2012. Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams. IACR Cryptol. ePrint Arch. (2012) 218. http:\/\/eprint.iacr.org\/2012\/218"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274608"},{"key":"e_1_3_2_1_13_1","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Durfee David","year":"2019","unstructured":"David Durfee and Ryan M Rogers. 2019. Practical differentially private top-k selection with pay-what-you-get composition. Advances in Neural Information Processing Systems , Vol. 32 (2019)."},{"key":"e_1_3_2_1_14_1","volume-title":"Theory of cryptography conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265--284."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2015.2425831"},{"key":"e_1_3_2_1_18_1","unstructured":"Badih Ghazi Noah Golowich Ravi Kumar Rasmus Pagh and Ameya Velingker. 2019. On the Power of Multiple Anonymous Messages. IACR Cryptol. ePrint Arch. (2019) 1382. https:\/\/eprint.iacr.org\/2019\/1382"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076828X"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2207.13793"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Aleksandra Korolova Krishnaram Kenthapadi Nina Mishra and Alexandros Ntoulas. 2009. Releasing search queries and clicks privately. In WWW. ACM 171--180. https:\/\/doi.org\/10.1145\/1526709.1526733","DOI":"10.1145\/1526709.1526733"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989290"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167--6423(82)90012-0"},{"key":"e_1_3_2_1_24_1","first-page":"25631","article-title":"Improved Utility Analysis of Private CountSketch","volume":"35","author":"Pagh Rasmus","year":"2022","unstructured":"Rasmus Pagh and Mikkel Thorup. 2022. Improved Utility Analysis of Private CountSketch. In Advances in Neural Information Processing Systems, Vol. 35. 25631--25643. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/a47f5cdff1469751597d78e803fc590f-Paper-Conference.pdf","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_25_1","volume-title":"International Conference on Machine Learning. PMLR, 8672--8681","author":"Qiao Gang","year":"2021","unstructured":"Gang Qiao, Weijie Su, and Li Zhang. 2021. Oneshot differentially private top-k selection. In International Conference on Machine Learning. PMLR, 8672--8681."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978409"},{"key":"e_1_3_2_1_27_1","volume-title":"Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private. arXiv preprint arXiv:2211.03695","author":"Jakub Tve","year":"2022","unstructured":"Jakub Tve tek. 2022. Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private. arXiv preprint arXiv:2211.03695 (2022)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2019.2927695"},{"key":"e_1_3_2_1_29_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 7766--7798","author":"Wu Hao","year":"2022","unstructured":"Hao Wu and Anthony Wirth. 2022. Asymptotically Optimal Locally Private Heavy Hitters via Parameterized Sketches. In International Conference on Artificial Intelligence and Statistics. PMLR, 7766--7798."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-021-0412-y"},{"key":"e_1_3_2_1_31_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. 2022a. Differentially Private Linear Sketches: Efficient Implementations and Applications. In Advances in Neural Information Processing Systems, Vol. 35. 12691--12704. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/525338e0d98401a62950bc7c454eb83d-Paper-Conference.pdf","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_32_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 3837--3847","author":"Zhu Wennan","year":"2020","unstructured":"Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Wei Li. 2020. Federated heavy hitters discovery with differential privacy. In International Conference on Artificial Intelligence and Statistics. PMLR, 3837--3847. io"}],"event":{"name":"SIGMOD\/PODS '23: International Conference on Management of Data","location":"Seattle WA USA","acronym":"SIGMOD\/PODS '23","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588673","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:28Z","timestamp":1750178788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":32,"alternative-id":["10.1145\/3584372.3588673","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3588673","relation":{},"subject":[],"published":{"date-parts":[[2023,6,18]]},"assertion":[{"value":"2023-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}