{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:02Z","timestamp":1755906002711,"version":"3.44.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1844234"],"award-info":[{"award-number":["CCF-1844234"]}],"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,9]]},"abstract":"<jats:p>\n            This paper considers statistical analysis on noisy datasets where near-duplicate elements need to be treated as identical ones. We focus on two basic problems, distinct elements and \u2113\n            <jats:sub>0<\/jats:sub>\n            -sampling, in the data stream model where the sequence of elements can only be scanned once using a limited space, under which a comprehensive data deduplication step before statistical analysis is not feasible. Previous streaming algorithms for these problems could only handle noisy datasets in\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (1)-dimensional Euclidean spaces. In this paper, we propose sublinear-space streaming algorithms that work for noisy datasets in any metric space. We also give a lower bound result showing that solving the distinct elements problem on noisy datasets in general metric spaces is inherently more difficult than solving it on noiseless datasets and on noisy datasets in\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (1)-dimensional Euclidean spaces.\n          <\/jats:p>","DOI":"10.1145\/3725248","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6851-3115","authenticated-orcid":false,"given":"Qin","family":"Zhang","sequence":"first","affiliation":[{"name":"Indiana University, Bloomington, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884528"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007379"},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"RANDOM","author":"Bar-Yossef Ziv","year":"2002","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In RANDOM, pages 1--10, 2002."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_9_1","first-page":"1433","volume-title":"SIGMOD","author":"Chen Di","year":"2016","unstructured":"Di Chen and Qin Zhang. Streaming algorithms for robust distinct elements. In Fatma \u00d6zcan, Georgia Koutrika, and Sam Madden, editors, SIGMOD, pages 1433--1447. ACM, 2016."},{"key":"e_1_2_1_10_1","first-page":"369","volume-title":"PODS","author":"Chen Jiecao","year":"2018","unstructured":"Jiecao Chen and Qin Zhang. Distinct sampling on streaming data with near-duplicates. In Jan Van den Bussche and Marcelo Arenas, editors, PODS, pages 369--382. ACM, 2018."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884527"},{"key":"e_1_2_1_12_1","first-page":"1234","volume-title":"SODA","author":"Chitnis Rajesh Hemant","year":"2015","unstructured":"Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh. Parameterized streaming: Maximal matching and vertex cover. In SODA, pages 1234--1251, 2015."},{"key":"e_1_2_1_13_1","first-page":"25","volume-title":"VLDB","author":"Cormode Graham","year":"2005","unstructured":"Graham Cormode, S. Muthukrishnan, and Irina Rozenbaum. Summarizing and mining inverse distributions on data streams via dynamic inverse sampling. In VLDB, pages 25--36, 2005."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687620"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_55"},{"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":"DMTCS Proceedings, (1)","author":"Flajolet Philippe","year":"2008","unstructured":"Philippe Flajolet, \u00c9ric Fusy, Olivier Gandouet, and Fr\u00e9d\u00e9ric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. DMTCS Proceedings, (1), 2008."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002520"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.031"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250866"},{"key":"e_1_2_1_22_1","first-page":"281","volume-title":"SPAA","author":"Phillip","year":"2001","unstructured":"Phillip B. Gibbons and Srikanta Tirthapura. Estimating simple functions on the union of data streams. In SPAA, pages 281--291, 2001."},{"key":"e_1_2_1_23_1","first-page":"913","volume-title":"STOC","author":"Haah Jeongwan","year":"2016","unstructured":"Jeongwan Haah, Aram W. Harrow, Zheng-Feng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Daniel Wichs and Yishay Mansour, editors, STOC, pages 913--925. ACM, 2016."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1534235"},{"key":"e_1_2_1_25_1","first-page":"604","volume-title":"STOC","author":"Indyk Piotr","year":"1998","unstructured":"Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Jeffrey Scott Vitter, editor, STOC, pages 604--613. ACM, 1998."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_2_1_28_1","volume-title":"The one-way communication complexity of the boolean hidden matching problem. CoRR, abs\/quant-ph\/0607173","author":"Kerenidis Iordanis","year":"2006","unstructured":"Iordanis Kerenidis and Ran Raz. The one-way communication complexity of the boolean hidden matching problem. CoRR, abs\/quant-ph\/0607173, 2006."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_70"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142599"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17, 1990","author":"Nisan Noam","year":"1990","unstructured":"Noam Nisan. Psuedorandom generators for space-bounded computation. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17, 1990, Baltimore, Maryland, USA, pages 204--212. ACM, 1990."},{"key":"e_1_2_1_33_1","first-page":"899","volume-title":"STOC","author":"O'Donnell Ryan","year":"2016","unstructured":"Ryan O'Donnell and John Wright. Efficient quantum tomography. In Daniel Wichs and Yishay Mansour, editors, STOC, pages 899--912. ACM, 2016."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_35_1","first-page":"222","volume-title":"18th Annual Symposium on Foundations of Computer Science","author":"Chi-Chih Yao Andrew","year":"1977","unstructured":"Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pages 222--227. IEEE Computer Society, 1977."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755575"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:16Z","timestamp":1755904696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725248"],"URL":"https:\/\/doi.org\/10.1145\/3725248","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}