{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:48:40Z","timestamp":1774986520158,"version":"3.50.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006374","name":"Ant Group","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Accurately estimating the number of unique elements that appear in data streams in real time is a fundamental problem with applications including network traffic monitoring and real-time social media analytics. Traditional sketch-based algorithms such as FM Sketch and HyperLogLog offer memory-friendly solutions for cardinality estimation but fall short in scenarios where the stream elements are privacy-sensitive and require differential privacy. Although recent approaches have incorporated differential privacy into the above cardinality estimators, they are limited to single-query settings, restricting their applicability. Previous methods for private cardinality continual release settings-i.e., releasing the cardinality after each new element in the stream-demand large memory resources and are thus difficult to apply in practice. In this paper, we present a novel cardinality estimation framework, FC, which ensures differential privacy under continual releases while simultaneously achieving low memory usage, high accuracy, and efficient computation. Our approach innovatively leverages an efficient cardinality estimator and privacy-preserving mechanisms to overcome the limitations of existing methods. Comprehensive experiments demonstrate that our method reduces memory usage by up to 504 times compared to the best previous method while maintaining nearly the same accuracy. Additionally, under identical memory constraints, our method improves the estimation accuracy by orders of magnitude.<\/jats:p>","DOI":"10.1145\/3725288","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":1,"title":["Efficient and Accurate Differentially Private Cardinality Continual Releases"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-8727-4946","authenticated-orcid":false,"given":"Dongdong","family":"Xie","sequence":"first","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China and OceanBase, Ant Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1434-837X","authenticated-orcid":false,"given":"Pinghui","family":"Wang","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8989-9662","authenticated-orcid":false,"given":"Quanqing","family":"Xu","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3530-6476","authenticated-orcid":false,"given":"Chuanhui","family":"Yang","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0354-9536","authenticated-orcid":false,"given":"Rundong","family":"Li","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02350-7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_1_5_1","volume-title":"Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1--24","author":"Hubert Chan T-H","year":"2011","unstructured":"T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1--24, 2011."},{"key":"e_1_2_1_6_1","volume-title":"Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. arXiv preprint arXiv:2301.05605","author":"Epasto Alessandro","year":"2023","unstructured":"Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. arXiv preprint arXiv:2301.05605, 2023."},{"key":"e_1_2_1_7_1","first-page":"26","article-title":"Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London","volume":"2","author":"Honaker James","year":"2015","unstructured":"James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26--27, 2015.","journal-title":"UK"},{"key":"e_1_2_1_8_1","volume-title":"Private online prefix sums via optimal matrix factorizations. arXiv e-prints","author":"McMahan Brendan","year":"2022","unstructured":"Brendan McMahan, Keith Rush, and Abhradeep Guha Thakurta. Private online prefix sums via optimal matrix factorizations. arXiv e-prints, pages arXiv--2202, 2022."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-0428"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch183"},{"key":"e_1_2_1_11_1","first-page":"10072","volume-title":"International Conference on Machine Learning","author":"Fichtenberger Hendrik","year":"2023","unstructured":"Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In International Conference on Machine Learning, pages 10072--10092. PMLR, 2023."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484750"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384297"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654931"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.46"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_17_1","first-page":"19561","article-title":"The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space","volume":"33","author":"Smith Adam","year":"2020","unstructured":"Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. Advances in Neural Information Processing Systems, 33:19561--19572, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-1106"},{"key":"e_1_2_1_19_1","unstructured":"Jeremiah Blocki Elena Grigorescu Tamalika Mukherjee and Samson Zhou. How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. In Nicole Megow and Adam Smith editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2023) volume 275 of Leibniz International Proceedings in Informatics (LIPIcs) pages 59:1--59:24 Dagstuhl Germany 2023. Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448530"},{"key":"e_1_2_1_21_1","first-page":"1","volume-title":"14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Ghazi Badih","year":"2023","unstructured":"Badih Ghazi, Ravi Kumar, Jelani Nelson, and Pasin Manurangsi. Private Counting of Distinct and k-Occurring Items in Time Windows. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1--55:24, Dagstuhl, Germany, 2023. Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_22_1","first-page":"36","article-title":"Counting distinct elements in the turnstile model with differential privacy under continual observation","author":"Jain Palak","year":"2024","unstructured":"Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. Advances in Neural Information Processing Systems, 36, 2024.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_23_1","volume-title":"The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9(3--4):211--407","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9(3--4):211--407, 2014."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179466"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_1_26_1","volume-title":"Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2):182--209","author":"Flajolet Philippe","year":"1985","unstructured":"Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2):182--209, 1985."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588914"},{"key":"e_1_2_1_28_1","series-title":"SIAM journal on computing, 31(6):1794--1813","volume-title":"Maintaining stream statistics over sliding windows","author":"Datar Mayur","year":"2002","unstructured":"Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM journal on computing, 31(6):1794--1813, 2002."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_30_1","volume-title":"Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis","author":"Mitzenmacher Michael","year":"2017","unstructured":"Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017."},{"key":"e_1_2_1_31_1","volume-title":"Statistical meta-analysis with applications","author":"Hartung Joachim","year":"2011","unstructured":"Joachim Hartung, Guido Knapp, and Bimal K Sinha. Statistical meta-analysis with applications. John Wiley & Sons, 2011."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_33_1","volume-title":"A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems (TODS), 15(2):208--229","author":"Whang Kyu-Young","year":"1990","unstructured":"Kyu-Young Whang, Brad T Vander-Zanden, and Howard M Taylor. A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems (TODS), 15(2):208--229, 1990."},{"key":"e_1_2_1_34_1","first-page":"605","volume-title":"Proceedings 11","author":"Durand Marianne","year":"2003","unstructured":"Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities. In Algorithms-ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16--19, 2003. Proceedings 11, pages 605--617. Springer, 2003."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554830"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611560"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_38_1","unstructured":"Openaddresses the free and open global address collection. https:\/\/openaddresses.io\/."},{"key":"e_1_2_1_39_1","unstructured":"North Carolina voter registration data. https:\/\/www.ncsbe.gov\/results-data\/voter-registration-data."},{"key":"e_1_2_1_40_1","unstructured":"The CAIDA UCSD Anonymized Internet Traces - 2024. https:\/\/www.caida.org\/catalog\/datasets\/passive_dataset."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1603899.1603924"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.23919\/cje.2023.00.332"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639281"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.23919\/cje.2021.00.411"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2019.23535"},{"key":"e_1_2_1_47_1","volume-title":"Differentially private continual release of graph statistics. arXiv preprint arXiv:1809.02575","author":"Song Shuang","year":"2018","unstructured":"Shuang Song, Susan Little, Sanjay Mehta, Staal Vinterbo, and Kamalika Chaudhuri. Differentially private continual release of graph statistics. arXiv preprint arXiv:1809.02575, 2018."},{"key":"e_1_2_1_48_1","volume-title":"Differentially private algorithms for graphs under continual observation. arXiv preprint arXiv:2106.14756","author":"Fichtenberger Hendrik","year":"2021","unstructured":"Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. Differentially private algorithms for graphs under continual observation. arXiv preprint arXiv:2106.14756, 2021."},{"key":"e_1_2_1_49_1","first-page":"26","article-title":"optimal algorithms for private online learning in full-information and bandit settings","author":"Thakurta Abhradeep Guha","year":"2013","unstructured":"Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances in Neural Information Processing Systems, 26, 2013.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_50_1","first-page":"32","volume-title":"International Conference on Machine Learning","author":"Agarwal Naman","year":"2017","unstructured":"Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In International Conference on Machine Learning, pages 32--40. PMLR, 2017."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48800-3_30"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-47534-9_9"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_1_54_1","volume-title":"New cardinality estimation algorithms for hyperloglog sketches. arXiv preprint arXiv:1702.01284","author":"Ertl Otmar","year":"2017","unstructured":"Otmar Ertl. New cardinality estimation algorithms for hyperloglog sketches. arXiv preprint arXiv:1702.01284, 2017."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00110"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057088"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539246"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3359710"},{"key":"e_1_2_1_59_1","volume-title":"Private counting of distinct elements in the turnstile model and extensions. arXiv preprint arXiv:2408.11637","author":"Henzinger Monika","year":"2024","unstructured":"Monika Henzinger, AR Sricharan, and Teresa Anna Steiner. Private counting of distinct elements in the turnstile model and extensions. arXiv preprint arXiv:2408.11637, 2024."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725288","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:53:02Z","timestamp":1774983182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725288"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725288"],"URL":"https:\/\/doi.org\/10.1145\/3725288","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}