{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T12:35:12Z","timestamp":1762432512660,"version":"3.41.0"},"reference-count":52,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62276066","U2241212"],"award-info":[{"award-number":["62276066","U2241212"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"New Cornerstone Science Foundation"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1109\/tit.2025.3550192","type":"journal-article","created":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T17:33:37Z","timestamp":1741714417000},"page":"4515-4536","source":"Crossref","is-referenced-by-count":1,"title":["Space Complexity of Euclidean Clustering"],"prefix":"10.1109","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-5587-4752","authenticated-orcid":false,"given":"Xiaoyi","family":"Zhu","sequence":"first","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1933-1538","authenticated-orcid":false,"given":"Yuxiang","family":"Tian","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7512-142X","authenticated-orcid":false,"given":"Lingxiao","family":"Huang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Novel Software Technology and the New Cornerstone Science Laboratory, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2671-7483","authenticated-orcid":false,"given":"Zengfeng","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref1","first-page":"1027","article-title":"K-means++: The advantages of careful seeding","volume-title":"Proc. 18th Annu. ACM-SIAM Symp. Discrete Algorithms","author":"Arthur"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35289-8_30"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00081"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451022"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519946"},{"key":"ref8","first-page":"2679","article-title":"Improved coresets for Euclidean k-means","volume-title":"Proc. Adv. Neural Inf. Process. Syst. 35, Annu. Conf. Neural Inf. Process. Syst.","author":"Cohen-Addad"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649707"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.102"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316307"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384296"},{"key":"ref14","first-page":"2012","article-title":"Approximate nearest neighbors in limited space","volume-title":"Proc. Conf. Learn. Theory","author":"Indyk"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.65"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/20M1371324"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.158"},{"key":"ref18","first-page":"576","article-title":"Clustering high dimensional dynamic data streams","volume-title":"Proc. ICML","volume":"70","author":"Braverman"},{"key":"ref19","article-title":"Nearly optimal dynamic k-means clustering for high-dimensional data","author":"Hu","year":"2018","journal-title":"arXiv:1802.00459"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.123"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002520"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585170"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.021"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00118"},{"article-title":"Near-optimal coresets for robust clustering","volume-title":"Proc. 11th Int. Conf. Learn. Represent.","author":"Huang","key":"ref25"},{"key":"ref26","first-page":"13891","article-title":"On coresets for clustering in small dimensional Euclidean spaces","volume-title":"Proc. ICML","volume":"202","author":"Huang"},{"key":"ref27","first-page":"1995","article-title":"Distributed k-means and k-median clustering on general topologies","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"26","author":"Balcan"},{"key":"ref28","first-page":"62:1","article-title":"Streaming coreset constructions for m-estimators","volume-title":"Proc. Approximation, Randomization, Combinat. Optim. Algorithms Techn. (APPROX\/RANDOM)","volume":"145","author":"Braverman"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00057"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.2307\/2000258"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519967"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.10.004"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"ref34","article-title":"New frameworks for offline and streaming coreset constructions","author":"Braverman","year":"2016","journal-title":"arXiv:1612.00889"},{"key":"ref35","first-page":"57:1","article-title":"Fully-dynamic coresets","volume-title":"Proc. 28th Annu. Eur. Symp. Algorithms","volume":"173","author":"Henzinger"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764938"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.64"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22935-0_53"},{"key":"ref39","first-page":"90989","article-title":"The space complexity of approximating logistic loss","volume-title":"Proc. 38th Annu. Conf. Neural Inf. Process. Syst.","author":"Dexter"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.90"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1968-0239742-X"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0264843-9"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.2307\/2005662"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80027-3"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1017\/9781108303453"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1002\/SERIES1345"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2023.127862"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/18M1209854"},{"volume-title":"Location-based Services","year":"2004","author":"Schiller","key":"ref49"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1145\/1961659.1961662"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63514"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/18\/11011509\/10922720.pdf?arnumber=10922720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T17:04:00Z","timestamp":1748019840000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10922720\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":52,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2025.3550192","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"type":"print","value":"0018-9448"},{"type":"electronic","value":"1557-9654"}],"subject":[],"published":{"date-parts":[[2025,6]]}}}