{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T13:31:02Z","timestamp":1787232662303,"version":"build-2736575974"},"reference-count":88,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Project A2"],"award-info":[{"award-number":["Project A2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["876"],"award-info":[{"award-number":["876"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Future and Emerging Technologies","award":["255827"],"award-info":[{"award-number":["255827"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Rev."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We develop and analyze a method to reduce the size of a very large set of data points in a high-dimensional Euclidean space [Formula: see text] to a small set of weighted points such that the result of a predetermined data analysis task on the reduced set is approximately the same as that for the original point set. For example, computing the first [Formula: see text] principal components of the reduced set will return approximately the first [Formula: see text] principal components of the original set, or computing the centers of a [Formula: see text]-means clustering on the reduced set will return an approximation for the original set. Such a reduced set is also known as a coreset. The main new features of our construction are that the cardinality of the reduced set is independent of the dimension [Formula: see text] of the input space and that the sets are mergeable [P. K. Agarwal et\u00a0al., Proceedings of the 31 st ACM SIGMOD-SIGACT-SIGAI Symposium on Principals of Database Systems, 2012, pp.\u00a023\u201334]. The latter property means that the union of two reduced sets is a reduced set for the union of the two original sets. It allows us to turn our methods into streaming or distributed algorithms using standard approaches. For problems such as [Formula: see text]-means and subspace approximation the coreset sizes are also independent of the number of input points. Our method is based on data-dependently projecting the points on a low-dimensional subspace and reducing the cardinality of the points inside this subspace using known methods. The proposed approach works for a wide range of data analysis techniques including [Formula: see text]-means clustering, principal component analysis, and subspace clustering. The main conceptual contribution is a new coreset definition that allows charging for the costs that appear for every solution to an additive constant.<\/jats:p>","DOI":"10.1137\/25m1799684","type":"journal-article","created":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T08:28:09Z","timestamp":1762417689000},"page":"801-861","source":"Crossref","is-referenced-by-count":0,"title":["Turning Big Data Into Tiny Data: Coresets for Unsupervised Learning Problems"],"prefix":"10.1137","volume":"67","author":[{"given":"Dan","family":"Feldman","sequence":"first","affiliation":[{"name":"Robotics & Big Data Lab, University of Haifa, Haifa, Israel, 3498838."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Melanie","family":"Schmidt","sequence":"additional","affiliation":[{"name":"Heinrich Heine University D\u00fcsseldorf, 40225 D\u00fcsseldorf, Germany.\u00a0The work of this author was also performed at TU Dortmund, the University of Bonn, and the University of Cologne."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[{"name":"University of Cologne, 50923 Cologne, Germany. The work of this author was performed at TU Dortmund."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,11,6]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/2133803.2184450"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, G. Cormode, Z. Huang, J. Phillips, Z. Wei, and K. Yi, Mergeable summaries, in Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS \u201912), ACM, New York, 2012, pp. 23\u201334, https:\/\/doi.org\/10.1145\/2213556.2213562.","DOI":"10.1145\/2213556.2213562"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A. Deshpande, and R. Kannan, Adaptive sampling for \\(k\\)-means clustering, in Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Springer, 2009, pp. 15\u201328.","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"ref6","unstructured":"D. Arthur and S. Vassilvitskii, k-means++: The advantages of careful seeding, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2007, pp. 1027\u20131035."},{"key":"ref7","unstructured":"P. Awasthi, M. Charikar, R. Krishnaswamy, and A. K. Sinop, The hardness of approximation of Euclidean k-means, in Proceedings of the 31st Symposium on Computational Geometry (SoCG 2015), LIPIcs, 34 (2015), pp. 754\u2013767."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"L. Becchetti, M. Bury, V. Cohen-Addad, F. Grandoni, and C. Schwiegelshohn, Oblivious dimension reduction for k-means: Beyond subspaces and the Johnson-Lindenstrauss lemma, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), ACM, 2019, pp. 1039\u20131050, https:\/\/doi.org\/10.1145\/3313276.3316318.","DOI":"10.1145\/3313276.3316318"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"ref12","unstructured":"C. Boutsidis, M. W. Mahoney, and P. Drineas, Unsupervised feature selection for the k-means clustering problem, in Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS), Curran Associates, 2009, pp. 153\u2013161."},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2375327"},{"key":"ref14","unstructured":"V. Braverman, D. Feldman, and H. Lang, New Frameworks for Offline and Streaming Coreset Constructions, preprint, arXiv:1612.00889, 2016."},{"key":"ref15","series-title":"Algorithms and Techniques (APPROX\/RANDOM 2019), LIPIcs","first-page":"62:1","volume-title":"Approximation, Randomization, and Combinatorial Optimization","volume":"145","author":"Braverman V.","year":"2019"},{"key":"ref16","unstructured":"V. Braverman, G. Frahling, H. Lang, C. Sohler, and L. F. Yang, Clustering high dimensional dynamic data streams, in Proceedings of the 34th International Conference on Machine Learning (ICML 2017), ACM, 2017, pp. 576\u2013585."},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"G. Camara, L. F. Assis, G. Ribeiro, K. R. Ferreira, E. Llapa, and L. Vinhas, Big earth observation data analytics: Matching requirements to system architectures, in Proceedings of the 5th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial \u201916), ACM, 2016, pp. 1\u20136, https:\/\/doi.org\/10.1145\/3006386.3006393.","DOI":"10.1145\/3006386.3006393"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and D. P. Woodruff, Numerical linear algebra in the streaming model, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), ACM, 2009, pp. 205\u2013214.","DOI":"10.1145\/1536414.1536445"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and D. P. Woodruff, Low rank approximation and regression in input sparsity time, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), ACM, 2013, pp. 81\u201390.","DOI":"10.1145\/2488608.2488620"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"M. B. Cohen, S. Elder, C. Musco, C. Musco, and M. Persu, Dimensionality reduction for k-means clustering and low rank approximation, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), ACM, 2015, pp. 163\u2013172.","DOI":"10.1145\/2746539.2746569"},{"key":"ref22","first-page":"11:1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), LIPIcs,\u00a055","author":"Cohen M. B.","year":"2016"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, H. Esfandiari, V. S. Mirrokni, and S. Narayanan, Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), ACM, 2022, pp. 1621\u20131628, https:\/\/doi.org\/10.1145\/3519935.3520011.","DOI":"10.1145\/3519935.3520011"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, C. S. Karthik, and E. Lee, Johnson coverage hypothesis: Inapproximability of k-means and k-median in \\(ell_p\\)-metrics, in Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1493\u20131530, https:\/\/doi.org\/10.1137\/1.9781611977073.63.","DOI":"10.1137\/1.9781611977073.63"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, P. N. Klein, and C. Mathieu, Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics, in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE,\u00a02016, pp. 353\u2013364.","DOI":"10.1109\/FOCS.2016.46"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, K. G. Larsen, D. Saulpic, and C. Schwiegelshohn, Towards optimal lower bounds for k-median and k-means coresets, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), ACM, 2022, pp. 1038\u20131051, https:\/\/doi.org\/10.1145\/3519935.3519946.","DOI":"10.1145\/3519935.3519946"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"2679","DOI":"10.52202\/068431-0194","volume-title":"Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022","author":"Cohen-Addad V.","year":"2022"},{"key":"ref28","unstructured":"V. Cohen-Addad, L. Wang, D. P. Woodruff, and S. Zhou, Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings, https:\/\/arxiv.org\/abs\/2504.16229, 2025."},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, D. P. Woodruff, and S. Zhou, Streaming Euclidean k-median and k-means with o(log n) space, in Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2023, pp. 883\u2013908, https:\/\/doi.org\/10.1109\/FOCS57990.2023.00057.","DOI":"10.1109\/FOCS57990.2023.00057"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"A. Deshpande and L. Rademacher, Efficient volume sampling for row\/column subset selection, in Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2010, pp. 329\u2013338.","DOI":"10.1109\/FOCS.2010.38"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a012"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"A. Deshpande, M. Tulsiani, and N. K. Vishnoi, Algorithms and hardness for subspace approximation, in Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2011, pp. 482\u2013496.","DOI":"10.1137\/1.9781611973082.39"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_28"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"M. Edwards and K. R. Varadarajan, No coreset, no cry: II, in Proceedings of the 25th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Springer, 2005, pp. 107\u2013115.","DOI":"10.1007\/11590156_8"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.10.004"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1335"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"D. Feldman, A. Fiat, and M. Sharir, Coresets for weighted facilities and their applications, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE,\u00a02006, pp. 315\u2013324.","DOI":"10.1109\/FOCS.2006.22"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"D. Feldman and M. Langberg, A unified framework for approximating and clustering data, in Proceedings of the 43rd ACM Symposium on the Theory of Computing (STOC 2011), ACM, 2011, pp. 569\u2013578, see http:\/\/arxiv.org\/abs\/1106.1379 for fuller version.","DOI":"10.1145\/1993636.1993712"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"D. Feldman, M. Monemizadeh, and C. Sohler, A PTAS for k-means clustering based on weak coresets, in Proceedings of the 23rd ACM Symposium on Computational Geometry (SoCG \u201907), ACM, 2007, pp. 11\u201318.","DOI":"10.1145\/1247069.1247072"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"D. Feldman, M. Monemizadeh, C. Sohler, and D. P. Woodruff, Coresets and sketches for high dimensional subspace approximation problems, in Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2010, pp. 630\u2013649, https:\/\/doi.org\/10.1137\/1.9781611973075.53.","DOI":"10.1137\/1.9781611973075.53"},{"key":"ref42","doi-asserted-by":"crossref","unstructured":"D. Feldman, M. Schmidt, and C. Sohler, Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering, in Proceedings of the 2013 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2013, pp. 1434\u20131453, https:\/\/doi.org\/10.1137\/1.9781611973105.103.","DOI":"10.1137\/1.9781611973105.103"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/18M1209854"},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"D. Feldman and L. J. Schulman, Data reduction for weighted and outlier-resistant clustering, in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2012, pp. 1343\u20131354, https:\/\/doi.org\/10.1137\/1.9781611973099.106.","DOI":"10.1137\/1.9781611973099.106"},{"key":"ref45","unstructured":"D. Feldman, M. Volkov, and D. Rus, Dimensionality Reduction of Massive Sparse Datasets Using Coresets, Advances in Neural Information Processing Systems 29, NIPS, 2016."},{"key":"ref46","unstructured":"D. Feldman, M. Volkov, and D. Rus, Dimensionality reduction of massive sparse datasets using coresets, in Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2016, Curran Associates, 2016, pp. 2766\u20132774, http:\/\/papers.nips.cc\/paper\/6596-dimensionality-reduction-of-massive-sparse-datasets-using-coresets."},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"H. Fichtenberger, M. Gill\u00e9, M. Schmidt, C. Schwiegelshohn, and C. Sohler, BICO: BIRCH meets coresets for k-means clustering, in Proceedings of the 21st Annual European Symposium on Algorithms (ESA), Springer, 2013, pp. 481\u2013492.","DOI":"10.1007\/978-3-642-40450-4_41"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"G. Frahling and C. Sohler, Coresets in dynamic geometric data streams, in Proceedings of the 37th ACM Symposium on the Theory of Computing (STOC 2025), ACM, 2005, pp. 209\u2013217.","DOI":"10.1145\/1060590.1060622"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"Z. Friggstad, M. Rezapour, and M. R. Salavatipour, Local search yields a PTAS for k-means in doubling metrics, in Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 365\u2013374.","DOI":"10.1109\/FOCS.2016.47"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1137\/15M1009718"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/0702016"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/BF02163027"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574058"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref55","doi-asserted-by":"crossref","unstructured":"S. Har-Peled, No coreset, no cry, in Proceedings of the 24th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Springer, 2004, pp. 324\u2013335.","DOI":"10.1007\/978-3-540-30538-5_27"},{"key":"ref56","doi-asserted-by":"crossref","unstructured":"S. Har-Peled, Coresets for discrete integration and clustering, in Proceedings of the 26th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Springer, 2006, pp. 33\u201344.","DOI":"10.1007\/11944836_6"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1271-x"},{"key":"ref58","doi-asserted-by":"crossref","unstructured":"S. Har-Peled and S. Mazumdar, Coresets for \\(k\\)-means and \\(k\\)-median clustering and their applications, in Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC 2004), ACM, 2004, pp. 291\u2013300.","DOI":"10.1145\/1007352.1007400"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9248-1"},{"key":"ref60","doi-asserted-by":"crossref","unstructured":"L. Huang, J. Li, and X. Wu, On optimal coreset construction for Euclidean (\\(k, z\\))-clustering, in Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), ACM, 2024, pp. 1594\u20131604, https:\/\/doi.org\/10.1145\/3618260.3649707.","DOI":"10.1145\/3618260.3649707"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667054"},{"key":"ref62","doi-asserted-by":"crossref","unstructured":"M. Langberg and L. J. Schulman, Universal \\(\\varepsilon\\)-approximators for integrals, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), SIAM, 2010, pp. 598\u2013607, https:\/\/doi.org\/10.1137\/1.9781611973075.50.","DOI":"10.1137\/1.9781611973075.50"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.11.009"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"ref65","doi-asserted-by":"crossref","unstructured":"E. Liberty, Simple and deterministic matrix sketching, in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2013, pp. 581\u2013588.","DOI":"10.1145\/2487575.2487623"},{"key":"ref66","doi-asserted-by":"crossref","unstructured":"M. Mahajan, P. Nimbhorkar, and K. R. Varadarajan, The planar \\(k\\)-means problem is NP-hard, in Proceedings of the 3rd Workshop on Algorithms and Computation (WALCOM), Springer, 2009, pp. 274\u2013285.","DOI":"10.1007\/978-3-642-00202-1_24"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"ref68","doi-asserted-by":"crossref","unstructured":"K. Makarychev, Y. Makarychev, and I. P. Razenshteyn, Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), ACM, 2019, pp. 1027\u20131038, https:\/\/doi.org\/10.1145\/3313276.3316350.","DOI":"10.1145\/3313276.3316350"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90039-6"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"ref71","doi-asserted-by":"crossref","unstructured":"N. H. Nguyen, T. T. Do, and T. D. Tran, A fast and efficient algorithm for low-rank approximation of a matrix, in Proceedings of the 41st ACM Symposium on the Theory of Computing (STOC 2009), ACM, 2009, pp. 215\u2013224.","DOI":"10.1145\/1536414.1536446"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1080\/14786440109462720"},{"key":"ref73","unstructured":"J. M. Phillips, Coresets and Sketches, https:\/\/arxiv.org\/abs\/1601.00617."},{"key":"ref74","doi-asserted-by":"crossref","unstructured":"J. M. Phillips and W. M. Tai, Improved coresets for kernel density estimates, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), SIAM, 2018, pp. 2718\u20132727, https:\/\/doi.org\/10.1137\/1.9781611975031.173.","DOI":"10.1137\/1.9781611975031.173"},{"key":"ref75","volume-title":"Numerical Mathematics","author":"Quarteroni A.","year":"2000"},{"key":"ref76","doi-asserted-by":"crossref","unstructured":"T. Sarl\u00f3s, Improved approximation algorithms for large matrices via random projections, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2006, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2006.37"},{"key":"ref77","unstructured":"M. Schmidt, Coresets and Streaming Algorithms for the k-Means Problem and Related Clustering Objectives, Ph.D. thesis, Universit\u00e4t Dortmund, 2014."},{"key":"ref78","first-page":"84:1","volume-title":"30th Annual European Symposium on Algorithms (ESA 2022) LIPIcs","volume":"244","author":"Schwiegelshohn C.","year":"2022"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9384-2"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1137\/1035134"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574"},{"key":"ref82","doi-asserted-by":"crossref","unstructured":"K. Varadarajan and X. Xiao, A near-linear algorithm for projective clustering integer points, in Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), SIAM, 2012, pp. 1329\u20131342, https:\/\/doi.org\/10.1137\/1.9781611973099.105.","DOI":"10.1137\/1.9781611973099.105"},{"key":"ref83","unstructured":"K. Varadarajan and X. Xiao, On the sensitivity of shape fitting problems, in Proceedings of the 32nd Annual Conference on IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2012, pp. 486\u2013497."},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0226281-1"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1080\/20964471.2019.1611175"},{"key":"ref87","doi-asserted-by":"crossref","unstructured":"D. Zermas, I. Izzat, and N. Papanikolopoulos, Fast segmentation of 3D point clouds: A paradigm on LiDAR data for autonomous vehicle applications, in 2017 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2017, pp. 5067\u20135073, https:\/\/doi.org\/10.1109\/ICRA.2017.7989591.","DOI":"10.1109\/ICRA.2017.7989591"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2025.3550192"}],"container-title":["SIAM Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/25M1799684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T13:12:47Z","timestamp":1787231567000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1799684"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,6]]},"references-count":88,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/25M1799684"],"URL":"https:\/\/doi.org\/10.1137\/25m1799684","relation":{},"ISSN":["0036-1445","1095-7200"],"issn-type":[{"value":"0036-1445","type":"print"},{"value":"1095-7200","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,6]]}}}