{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T13:12:41Z","timestamp":1778764361053,"version":"3.51.4"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T00:00:00Z","timestamp":1778716800000},"content-version":"vor","delay-in-days":2,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1844234"],"award-info":[{"award-number":["CCF-1844234"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,12]]},"abstract":"<jats:p>\n                    We propose a novel framework for statistical estimation on noisy datasets. Within this framework, we focus on the frequency moments (\n                    <jats:italic toggle=\"yes\">\n                      F\n                      <jats:sub>p<\/jats:sub>\n                    <\/jats:italic>\n                    ) problem and demonstrate that it is possible to approximate\n                    <jats:italic toggle=\"yes\">\n                      F\n                      <jats:sub>p<\/jats:sub>\n                    <\/jats:italic>\n                    of the unknown ground-truth dataset using sublinear space in the data stream model and sublinear communication in the coordinator model, provided that the approximation ratio is parameterized by a data-dependent quantity, which we call the\n                    <jats:italic toggle=\"yes\">\n                      F\n                      <jats:sub>p<\/jats:sub>\n                    <\/jats:italic>\n                    -mismatch-ambiguity. We also establish a set of lower bounds, which are tight in terms of the input size. Our results yield several interesting insights:\n\n-In the data stream model, the\n                    <jats:italic toggle=\"yes\">\n                      F\n                      <jats:sub>p<\/jats:sub>\n                    <\/jats:italic>\n                    problem is inherently more difficult in the noisy setting than in the noiseless one. In particular, while\n                    <jats:italic toggle=\"yes\">F<\/jats:italic>\n                    <jats:sub>2<\/jats:sub>\n                    can be approximated in logarithmic space in terms of the input size in the noiseless setting, any algorithm for\n                    <jats:italic toggle=\"yes\">F<\/jats:italic>\n                    <jats:sub>2<\/jats:sub>\n                    in the noisy setting requires polynomial space. \n\n-In the coordinator model, in sharp contrast to the noiseless case, achieving polylogarithmic communication in the input size is generally impossible for\n                    <jats:italic toggle=\"yes\">\n                      F\n                      <jats:sub>p<\/jats:sub>\n                    <\/jats:italic>\n                    under noise. However, when the\n                    <jats:italic toggle=\"yes\">\n                      F\n                      <jats:sub>p<\/jats:sub>\n                    <\/jats:italic>\n                    mismatch ambiguity falls below a certain threshold, it becomes possible to achieve communication that is entirely independent of the input size.\n                  <\/jats:p>","DOI":"10.1145\/3801901","type":"journal-article","created":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:50:22Z","timestamp":1778763022000},"page":"1-24","source":"Crossref","is-referenced-by-count":0,"title":["Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-7065-0404","authenticated-orcid":false,"given":"Kaiwen","family":"Liu","sequence":"first","affiliation":[{"name":"Indiana University, Bloomington, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6851-3115","authenticated-orcid":false,"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Indiana University, Bloomington, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","first-page":"6364","article-title":"High frequency moments via max-stability","author":"Andoni Alexandr","year":"2017","unstructured":"Alexandr Andoni. 2017. High frequency moments via max-stability. In ICASSP. 6364-6368.","journal-title":"ICASSP."},{"key":"e_1_2_1_3_1","first-page":"363","article-title":"Streaming Algorithms via Precision Sampling","author":"Andoni Alexandr","year":"2011","unstructured":"Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. 2011. Streaming Algorithms via Precision Sampling. In FOCS. 363-372.","journal-title":"FOCS."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1145\/1109557.1109634","article-title":"Simpler algorithm for estimating frequency moments of data streams","author":"Bhuvanagiri Lakshminath","year":"2006","unstructured":"Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha. 2006. Simpler algorithm for estimating frequency moments of data streams. In SODA. 708-713.","journal-title":"SODA."},{"key":"e_1_2_1_6_1","first-page":"360","article-title":"Optimality of Frequency Moment Estimation","author":"Braverman Mark","year":"2025","unstructured":"Mark Braverman and Or Zamir. 2025. Optimality of Frequency Moment Estimation. In STOC. 360-370.","journal-title":"STOC."},{"key":"e_1_2_1_7_1","volume-title":"Recursive Sketching For Frequency Moments. CoRR","author":"Braverman Vladimir","year":"2010","unstructured":"Vladimir Braverman and Rafail Ostrovsky. 2010. Recursive Sketching For Frequency Moments. CoRR, Vol. abs\/1011.2571 (2010)."},{"key":"e_1_2_1_8_1","volume-title":"APPROX-RANDOM (Lecture Notes in Computer Science","volume":"70","author":"Braverman Vladimir","year":"2013","unstructured":"Vladimir Braverman and Rafail Ostrovsky. 2013. Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams. In APPROX-RANDOM (Lecture Notes in Computer Science, Vol. 8096), Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and Jos\u00e9 D. P. Rolim (Eds.). Springer, 58-70."},{"key":"e_1_2_1_9_1","first-page":"107","article-title":"Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness","author":"Chakrabarti Amit","year":"2003","unstructured":"Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. 2003. Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. In CCC. IEEE Computer Society, 107-117.","journal-title":"CCC. IEEE Computer Society"},{"key":"e_1_2_1_10_1","first-page":"1433","article-title":"Streaming Algorithms for Robust Distinct Elements. In SIGMOD, Fatma \u00d6zcan, Georgia Koutrika, and Sam Madden (Eds.)","author":"Chen Di","year":"2016","unstructured":"Di Chen and Qin Zhang. 2016. Streaming Algorithms for Robust Distinct Elements. In SIGMOD, Fatma \u00d6zcan, Georgia Koutrika, and Sam Madden (Eds.). ACM, 1433-1447.","journal-title":"ACM"},{"key":"e_1_2_1_11_1","first-page":"369","article-title":"Distinct Sampling on Streaming Data with Near-Duplicates. In PODS, Jan Van den Bussche and Marcelo Arenas (Eds.)","author":"Chen Jiecao","year":"2018","unstructured":"Jiecao Chen and Qin Zhang. 2018. Distinct Sampling on Streaming Data with Near-Duplicates. In PODS, Jan Van den Bussche and Marcelo Arenas (Eds.). ACM, 369-382.","journal-title":"ACM"},{"key":"e_1_2_1_12_1","volume-title":"Garofalakis","author":"Cormode Graham","year":"2007","unstructured":"Graham Cormode and Minos N. Garofalakis. 2007. Sketching probabilistic data streams. In SIGMOD, Chee Yong Chan, Beng Chin Ooi, and Aoying Zhou (Eds.). ACM, 281-292."},{"key":"e_1_2_1_13_1","first-page":"1076","article-title":"Algorithms for distributed functional monitoring","author":"Cormode Graham","year":"2008","unstructured":"Graham Cormode, S. Muthukrishnan, and Ke Yi. 2008. Algorithms for distributed functional monitoring. In SODA. 1076-1085.","journal-title":"SODA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160163"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687620"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.250581"},{"key":"e_1_2_1_17_1","volume-title":"ACM","author":"Esfandiari Hossein","year":"2024","unstructured":"Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, and Peilin Zhong. 2024. Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. In STOC, Bojan Mohar, Igor Shinkar, and Ryan O'Donnell (Eds.). ACM, 1911-1922."},{"key":"e_1_2_1_18_1","first-page":"594","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"Feige Uriel","year":"2004","unstructured":"Uriel Feige. 2004. On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, L\u00e1szl\u00f3 Babai (Ed.). ACM, 594-603."},{"key":"e_1_2_1_19_1","volume-title":"Polynomial Estimators for High Frequency Moments. CoRR","author":"Ganguly Sumit","year":"2011","unstructured":"Sumit Ganguly. 2011. Polynomial Estimators for High Frequency Moments. CoRR, Vol. abs\/1104.4552 (2011)."},{"key":"e_1_2_1_20_1","volume-title":"A Lower Bound for Estimating High Moments of a Data Stream. CoRR","author":"Ganguly Sumit","year":"2012","unstructured":"Sumit Ganguly. 2012. A Lower Bound for Estimating High Moments of a Data Stream. CoRR, Vol. abs\/1201.0253 (2012)."},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"High Probability Frequency Moment Sketches. In ICALP (LIPIcs, Vol. 107), Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.)","volume":"58","author":"Ganguly Sumit","year":"2018","unstructured":"Sumit Ganguly and David P. Woodruff. 2018. High Probability Frequency Moment Sketches. In ICALP (LIPIcs, Vol. 107), Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 58:1-58:15.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_22_1","volume-title":"Data quality and record linkage techniques","author":"Herzog Thomas N","unstructured":"Thomas N Herzog, Fritz J Scheuren, and William E Winkler. 2007. Data quality and record linkage techniques. Vol. 1. Springer."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1145\/3717823.3718199","volume-title":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague","author":"Huang Zengfeng","year":"2025","unstructured":"Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu, and Zhewei Wei. 2025. Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, Michal Kouck\u00fd, and Nikhil Bansal (Eds.). ACM, 371-382."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/1060590.1060621","article-title":"Optimal approximations of the frequency moments of data streams","author":"Indyk Piotr","year":"2005","unstructured":"Piotr Indyk and David P. Woodruff. 2005. Optimal approximations of the frequency moments of data streams. In STOC. 202-208.","journal-title":"STOC."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3596494"},{"key":"e_1_2_1_26_1","volume-title":"Efficient aggregation algorithms for probabilistic data","author":"Jayram T. S.","unstructured":"T. S. Jayram, Satyen Kale, and Erik Vee. 2007a. Efficient aggregation algorithms for probabilistic data. In SODA, Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 346-355."},{"key":"e_1_2_1_27_1","first-page":"243","article-title":"Estimating statistical aggregates on probabilistic data streams. In PODS, Leonid Libkin (Ed.)","author":"Jayram T. S.","year":"2007","unstructured":"T. S. Jayram, Andrew McGregor, S. Muthukrishnan, and Erik Vee. 2007b. Estimating statistical aggregates on probabilistic data streams. In PODS, Leonid Libkin (Ed.). ACM, 243-252.","journal-title":"ACM"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453892"},{"key":"e_1_2_1_29_1","volume-title":"Principal Component Analysis and Higher Correlations for Distributed Data. In COLT (JMLR Workshop and Conference Proceedings","volume":"1057","author":"Kannan Ravi","unstructured":"Ravi Kannan, Santosh S. Vempala, and David P. Woodruff. 2014. Principal Component Analysis and Higher Correlations for Distributed Data. In COLT (JMLR Workshop and Conference Proceedings, Vol. 35). 1040-1057."},{"key":"e_1_2_1_30_1","first-page":"802","article-title":"Record linkage: similarity measures and algorithms","author":"Koudas Nick","year":"2006","unstructured":"Nick Koudas, Sunita Sarawagi, and Divesh Srivastava. 2006. Record linkage: similarity measures and algorithms. In SIGMOD. ACM, 802-803.","journal-title":"SIGMOD. ACM"},{"key":"e_1_2_1_31_1","volume-title":"Woodruff","author":"Li Yi","year":"2013","unstructured":"Yi Li and David P. Woodruff. 2013. A Tight Lower Bound for High Frequency Moment Estimation with Small Error. In APPROX-RANDOM (Lecture Notes in Computer Science, Vol. 8096), Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and Jos\u00e9 D. P. Rolim (Eds.). Springer, 623-638."},{"key":"e_1_2_1_32_1","unstructured":"Kaiwen Liu and Qin Zhang. 2026. Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity. arXiv:2603.11216 [cs.DS] https:\/\/arxiv.org\/abs\/2603.11216"},{"key":"e_1_2_1_33_1","first-page":"1143","article-title":"1-Pass Relative-Error L()-Sampling with Applications","author":"Monemizadeh Morteza","year":"2010","unstructured":"Morteza Monemizadeh and David P. Woodruff. 2010. 1-Pass Relative-Error L()-Sampling with Applications. In SODA. 1143-1160.","journal-title":"SODA."},{"key":"e_1_2_1_34_1","volume-title":"Lower bounds for number-in-hand multiparty communication complexity, made easy","author":"Phillips Jeff M.","unstructured":"Jeff M. Phillips, Elad Verbin, and Qin Zhang. 2012. Lower bounds for number-in-hand multiparty communication complexity, made easy. In SODA, Yuval Rabani (Ed.). SIAM, 486-501."},{"key":"e_1_2_1_35_1","first-page":"167","article-title":"Optimal space lower bounds for all frequency moments","author":"Woodruff David P.","year":"2004","unstructured":"David P. Woodruff. 2004. Optimal space lower bounds for all frequency moments. In SODA. 167-175.","journal-title":"SODA."},{"key":"e_1_2_1_36_1","volume-title":"Woodruff and Qin Zhang","author":"David","year":"2012","unstructured":"David P. Woodruff and Qin Zhang. 2012. Tight bounds for distributed functional monitoring. In STOC, Howard J. Karloff and Toniann Pitassi (Eds.). ACM, 941-960."},{"key":"e_1_2_1_37_1","first-page":"313","article-title":"Communication-Efficient Computation on Distributed Noisy Datasets","author":"Zhang Qin","year":"2015","unstructured":"Qin Zhang. 2015. Communication-Efficient Computation on Distributed Noisy Datasets. In SPAA. 313-322.","journal-title":"SPAA."},{"key":"e_1_2_1_38_1","volume-title":"Proc. ACM Manag. Data","volume":"3","author":"Zhang Qin","year":"2025","unstructured":"Qin Zhang. 2025. Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces. Proc. ACM Manag. Data, Vol. 3, 2 (2025), 111:1-111:25."},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Quantum Data Sketches. In ICDT (LIPIcs, Vol. 328), Sudeepa Roy and Ahmet Kara (Eds.)","volume":"16","author":"Zhang Qin","year":"2025","unstructured":"Qin Zhang and Mohsen Heidari. 2025. Quantum Data Sketches. In ICDT (LIPIcs, Vol. 328), Sudeepa Roy and Ahmet Kara (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 16:1-16:19.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_40_1","first-page":"819","article-title":"Finding frequent items in probabilistic data. In SIGMOD, Jason Tsong-Li Wang (Ed.)","author":"Zhang Qin","year":"2008","unstructured":"Qin Zhang, Feifei Li, and Ke Yi. 2008. Finding frequent items in probabilistic data. In SIGMOD, Jason Tsong-Li Wang (Ed.). ACM, 819-832.","journal-title":"ACM"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801901","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:52:53Z","timestamp":1778763173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3801901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,12]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,12]]}},"alternative-id":["10.1145\/3801901"],"URL":"https:\/\/doi.org\/10.1145\/3801901","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,12]]}}}