{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:57:40Z","timestamp":1781326660479,"version":"3.54.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62272372, 62272379"],"award-info":[{"award-number":["62272372, 62272379"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003816","name":"Huawei Technologies","doi-asserted-by":"publisher","award":["CCF-HuaweiDB202407"],"award-info":[{"award-number":["CCF-HuaweiDB202407"]}],"id":[{"id":"10.13039\/501100003816","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,9,22]]},"abstract":"<jats:p>\n                    Counting the number of distinct values (NDV) is a fundamental problem in web applications and databases, particularly under memory constraints. Sketch-based methods, such as the Flajolet-Martin sketch, construct compact data summaries to estimate NDV but primarily focus on insertion-only scenarios. However, supporting delete operations is crucial for maintaining accurate and up-to-date cardinality estimates in many real-world applications, such as databases. Existing methods for fully dynamic scenarios, involving both insertions and deletions, often incur considerable computational and memory overhead. Furthermore, collaborative computation often requires sharing sketches with external or untrusted parties, which introduces significant privacy risks. To address these challenges, we propose a novel sketch method,\n                    <jats:italic toggle=\"yes\">GMod,<\/jats:italic>\n                    specifically designed for fully dynamic scenarios and compatible with local differential privacy (LDP) for both NDV estimation and privacy preservation. Our method supports efficient deletions with minimal additional overhead by utilizing a single discrete uniformly distributed random variable. Additionally, we introduce a lightweight probabilistic estimation model to compute NDV, achieving 3\u00d7 faster performance compared to the state-of-the-art. By incorporating carefully designed sketch perturbation mechanisms, our model mitigates the impact of LDP noise. Experimental results demonstrate that our method uses 1\/3 of the memory to achieve comparable estimation accuracy in local settings and provides 8\u00d7 higher accuracy under LDP scenarios compared to state-of-the-art methods.\n                  <\/jats:p>","DOI":"10.1145\/3749157","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0857-4573","authenticated-orcid":false,"given":"Zhicheng","family":"Li","sequence":"first","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4761-0410","authenticated-orcid":false,"given":"Zeli","family":"Lin","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9718-9354","authenticated-orcid":false,"given":"Bichun","family":"Chen","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8727-4946","authenticated-orcid":false,"given":"Dongdong","family":"Xie","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335230"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6566977"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"2526","DOI":"10.1109\/INFCOM.2012.6195645","volume-title":"2012 Proceedings IEEE INFOCOM","author":"Li Tao","year":"2012","unstructured":"Tao Li, Shigang Chen, and Yan Qiao. Origin-destination flow measurement in high-speed networks. In 2012 Proceedings IEEE INFOCOM, pages 2526-2530. IEEE, 2012."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.031"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0065-y"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218625"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872790"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00149-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00101"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/571697.571699"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"3888","DOI":"10.1109\/GLOCOM.2003.1258959","volume-title":"GLOBECOM '03. IEEE Global Telecommunications Conference (IEEE Cat. No.03CH37489)","volume":"7","author":"Kim Hyang-Ah","year":"2003","unstructured":"Hyang-Ah Kim and D.R. O'Hallaron. Counting network flows in real time. In GLOBECOM '03. IEEE Global Telecommunications Conference (IEEE Cat. No.03CH37489), volume 7, pages 3888-3893 vol.7, 2003."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948225"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972979.9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2015.2463121"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/Blockchain53845.2021.00013"},{"key":"e_1_2_1_17_1","volume-title":"A framework for anomaly detection in blockchain networks with sketches","author":"Voronov Tomer","year":"2023","unstructured":"Tomer Voronov, Danny Raz, and Ori Rottenstreich. A framework for anomaly detection in blockchain networks with sketches. IEEE\/ACM Transactions on Networking, 2023."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMSNETS51098.2021.9352944"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2024.3372604"},{"key":"e_1_2_1_20_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_21_1","volume-title":"Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. Discrete mathematics & theoretical computer science (Proceedings)","author":"Flajolet Philippe","year":"2007","unstructured":"Philippe Flajolet, \u00c9ric Fusy, Olivier Gandouet, and Fr\u00e9d\u00e9ric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. Discrete mathematics & theoretical computer science (Proceedings), 2007."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_2_1_24_1","volume-title":"Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio, 1:1-39","author":"Freitag Michael","year":"2019","unstructured":"Michael Freitag and Thomas Neumann. Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio, 1:1-39, 2019."},{"key":"e_1_2_1_25_1","article-title":"A fully-dynamic sketch for estimating the number of distinct values in big tables","author":"Wang Pinghui","year":"2024","unstructured":"Pinghui Wang, Dongdong Xie, Junzhou Zhao, Jinsong Li, Zhicheng Li, Rundong Li, and Yang Ren. Half-xor: A fully-dynamic sketch for estimating the number of distinct values in big tables. IEEE Transactions on Knowledge and Data Engineering, 2024.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316718"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0135-3"},{"issue":"7","key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1109\/TC.1986.1676799","article-title":"Computer and database location in distributed computer systems","volume":"100","author":"Pirkul Gavish","year":"1986","unstructured":"Gavish and Pirkul. Computer and database location in distributed computer systems. IEEE Transactions on Computers, 100(7):583-590, 1986.","journal-title":"IEEE Transactions on Computers"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_32"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/PAC.2017.43"},{"key":"e_1_2_1_31_1","first-page":"965","volume-title":"30th USENIX security symposium (USENIX Security 21)","author":"Hu Changhui","year":"2021","unstructured":"Changhui Hu, Jin Li, Zheli Liu, Xiaojie Guo, Yu Wei, Xuan Guang, Grigorios Loukides, and Changyu Dong. How to make private distributed cardinality estimation practical, and get differential privacy for free. In 30th USENIX security symposium (USENIX Security 21), pages 965-982, 2021."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055518.3055528"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJWGS.2018.095647"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-1106"},{"key":"e_1_2_1_35_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_36_1","volume-title":"Cardinality estimators do not preserve privacy. arXiv preprint arXiv:1808.05879","author":"Desfontaines Damien","year":"2018","unstructured":"Damien Desfontaines, Andreas Lochbihler, and David Basin. Cardinality estimators do not preserve privacy. arXiv preprint arXiv:1808.05879, 2018."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134034"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588914"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35404-5_17"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2013.05.011"},{"key":"e_1_2_1_41_1","first-page":"12846","volume-title":"International Conference on Machine Learning","author":"Hehir Jonathan","year":"2023","unstructured":"Jonathan Hehir, Daniel Ting, and Graham Cormode. Sketch-flip-merge: Mergeable sketches for private distinct counting. In International Conference on Machine Learning, pages 12846-12865. PMLR, 2023."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"issue":"110","key":"e_1_2_1_43_1","first-page":"1","article-title":"Secure multi-party computation","volume":"78","author":"Goldreich Oded","year":"1998","unstructured":"Oded Goldreich. Secure multi-party computation. Manuscript. Preliminary version, 78(110):1-108, 1998.","journal-title":"Manuscript. Preliminary version"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"issue":"1","key":"e_1_2_1_45_1","first-page":"8829523","article-title":"A comprehensive survey on local differential privacy","volume":"2020","author":"Xiong Xingxing","year":"2020","unstructured":"Xingxing Xiong, Shubo Liu, Dan Li, Zhaohui Cai, and Xiaoguang Niu. A comprehensive survey on local differential privacy. Security and Communication Networks, 2020(1):8829523, 2020.","journal-title":"Security and Communication Networks"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1145\/2660267.2660348","volume-title":"Proceedings of the 2014 ACM SIGSAC conference on computer and communications security","author":"Erlingsson \u00dalfar","year":"2014","unstructured":"\u00dalfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014."},{"key":"e_1_2_1_47_1","unstructured":"Benjamin Kreuter Craig William Wright Evgeny Sergeevich Skvortsov Raimundo Mirisola and Yao Wang. Privacy-preserving secure cardinality and frequency estimation. Tech. Rep. Google LLC 2020."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.46"},{"key":"e_1_2_1_49_1","first-page":"2436","volume-title":"International Conference on Machine Learning","author":"Kairouz Peter","year":"2016","unstructured":"Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. In International Conference on Machine Learning, pages 2436-2444. PMLR, 2016."},{"key":"e_1_2_1_50_1","volume-title":"The Art of Computer Programming: Fundamental Algorithms","author":"Knuth Donald E","year":"1997","unstructured":"Donald E Knuth. The Art of Computer Programming: Fundamental Algorithms, Volume 1. Addison-Wesley Professional, 1997."},{"key":"e_1_2_1_51_1","first-page":"729","volume-title":"26th USENIX Security Symposium (USENIX Security 17)","author":"Wang Tianhao","year":"2017","unstructured":"Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17), pages 729-745, 2017."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-1694(99)00184-5"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.2012.687494"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781119558378"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588680"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639281"},{"key":"e_1_2_1_57_1","first-page":"1049","volume-title":"VLDB","volume":"6","author":"Nambiar Raghunath Othayoth","year":"2006","unstructured":"Raghunath Othayoth Nambiar and Meikel Poess. The making of tpc-ds. In VLDB, volume 6, pages 1049-1058, 2006."},{"key":"e_1_2_1_58_1","volume-title":"Bitcoinheist: Topological data analysis for ransomware detection on the bitcoin blockchain. arXiv preprint arXiv:1906.07852","author":"Akcora Cuneyt Gurcan","year":"2019","unstructured":"Cuneyt Gurcan Akcora, Yitao Li, Yulia R Gel, and Murat Kantarcioglu. Bitcoinheist: Topological data analysis for ransomware detection on the bitcoin blockchain. arXiv preprint arXiv:1906.07852, 2019."},{"key":"e_1_2_1_59_1","first-page":"30","article-title":"Practical hash functions for similarity estimation and dimensionality reduction","author":"Dahlgaard S\u00f8ren","year":"2017","unstructured":"S\u00f8ren Dahlgaard, Mathias Knudsen, and Mikkel Thorup. Practical hash functions for similarity estimation and dimensionality reduction. Advances in Neural Information Processing Systems, 30, 2017.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1002\/0470866993"},{"key":"e_1_2_1_62_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_63_1","volume-title":"Extendedhyperloglog: Analysis of a new cardinality estimator. arXiv preprint arXiv:2106.06525","author":"Ohayon Tal","year":"2021","unstructured":"Tal Ohayon. Extendedhyperloglog: Analysis of a new cardinality estimator. arXiv preprint arXiv:2106.06525, 2021."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539246"},{"key":"e_1_2_1_65_1","volume-title":"Ultraloglog: A practical and more space-efficient alternative to hyperloglog for approximate distinct counting. arXiv preprint arXiv:2308.16862","author":"Ertl Otmar","year":"2023","unstructured":"Otmar Ertl. Ultraloglog: A practical and more space-efficient alternative to hyperloglog for approximate distinct counting. arXiv preprint arXiv:2308.16862, 2023."},{"key":"e_1_2_1_66_1","volume-title":"Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60(309):63-69","author":"Warner Stanley L","year":"1965","unstructured":"Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60(309):63-69, 1965."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_68_1","volume-title":"Efficient differentially private $ f_0 $ linear sketching. arXiv preprint arXiv:2001.11932","author":"Pagh Rasmus","year":"2020","unstructured":"Rasmus Pagh and Nina Mesing Stausholm. Efficient differentially private $ f_0 $ linear sketching. arXiv preprint arXiv:2001.11932, 2020."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:37:23Z","timestamp":1781325443000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":68,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749157"],"URL":"https:\/\/doi.org\/10.1145\/3749157","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}