{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T20:56:42Z","timestamp":1764277002846,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T00:00:00Z","timestamp":1586822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Let P be a set of n points in     R d    ,     k \u2265 1     be an integer and     \u03b5 \u2208 ( 0 , 1 )     be a constant. An \u03b5-coreset is a subset     C \u2286 P     with appropriate non-negative weights (scalars), that approximates any given set     Q \u2286  R d      of k centers. That is, the sum of squared distances over every point in P to its closest point in Q is the same, up to a factor of     1 \u00b1 \u03b5     to the weighted sum of C to the same k centers. If the coreset is small, we can solve problems such as k-means clustering or its variants (e.g., discrete k-means, where the centers are restricted to be in P, or other restricted zones) on the small coreset to get faster provable approximations. Moreover, it is known that such coreset support streaming, dynamic and distributed data using the classic merge-reduce trees. The fact that the coreset is a subset implies that it preserves the sparsity of the data. However, existing such coresets are randomized and their size has at least linear dependency on the dimension d. We suggest the first such coreset of size independent of d. This is also the first deterministic coreset construction whose resulting size is not exponential in d. Extensive experimental results and benchmarks are provided on public datasets, including the first coreset of the English Wikipedia using Amazon\u2019s cloud.<\/jats:p>","DOI":"10.3390\/a13040092","type":"journal-article","created":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T04:01:46Z","timestamp":1586923306000},"page":"92","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Deterministic Coresets for k-Means of Big Sparse Data"],"prefix":"10.3390","volume":"13","author":[{"given":"Artem","family":"Barger","sequence":"first","affiliation":[{"name":"Department of Computer, Science University of Haifa, Haifa 32000, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7700-9711","authenticated-orcid":false,"given":"Dan","family":"Feldman","sequence":"additional","affiliation":[{"name":"Department of Computer, Science University of Haifa, Haifa 32000, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,4,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/1008731.1008736","article-title":"Approximating extent measures of points","volume":"51","author":"Agarwal","year":"2004","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Har-Peled, S., and Mazumdar, S. (2004, January 13\u201315). On coresets for k-means and k-median clustering. Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","key":"ref_2","DOI":"10.1145\/1007352.1007400"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","article-title":"Decomposable Searching Problems I: Static-to-Dynamic Transformation","volume":"1","author":"Bentley","year":"1980","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Feldman, D., Schmidt, M., and Sohler, C. (2013, January 6\u20138). Turning big data into tiny data: Constant-size coresets for k-means, pca and projective clustering. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA.","key":"ref_4","DOI":"10.1137\/1.9781611973105.103"},{"unstructured":"(2020, March 10). Apache Hadoop. Available online: http:\/\/hadoop.apache.org.","key":"ref_5"},{"doi-asserted-by":"crossref","unstructured":"Barger, A., and Feldman, D. (2016, January 5\u20137). k-means for Streaming and Distributed Big Sparse Data. Proceedings of the 2016 SIAM International Conference on Data Mining, Miami, FL, USA.","key":"ref_6","DOI":"10.1137\/1.9781611974348.39"},{"unstructured":"Feldman, D., Faulkner, M., and Krause, A. (2011, January 12\u201314). Scalable training of mixture models via coresets. Proceedings of the NIPS 2011\u2014Advances in Neural Information Processing Systems, Granada, Spain.","key":"ref_7"},{"unstructured":"Barger, A., and Feldman, D. Source code for running streaming SparseKMeans coreset on the cloud 2017, (in process).","key":"ref_8"},{"doi-asserted-by":"crossref","unstructured":"Chen, K. (2006, January 5\u20137). On k-median clustering in High Dimensions. Proceedings of the 17th Annu. ACM-SIAM Symposium on Discrete Algorithms (SODA), Barcelona, Spain.","key":"ref_9","DOI":"10.1145\/1109557.1109687"},{"doi-asserted-by":"crossref","unstructured":"Langberg, M., and Schulman, L.J. (2010, January 17\u201319). Universal \u03b5 approximators for integrals. Proceedings of the Twenty-First Annual ACM-SIAM symposium on Discrete Algorithms, Austin, TX, USA.","key":"ref_10","DOI":"10.1137\/1.9781611973075.50"},{"doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., and Sohler, C. (2007, January 6\u20138). A PTAS for k-means clustering based on weak coresets. Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, Gyeongju, South Korea.","key":"ref_11","DOI":"10.1145\/1247069.1247072"},{"unstructured":"Feldman, D., and Langberg, M. (2016). A Unified Framework for Approximating and Clustering Data. arXiv.","key":"ref_12"},{"doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., and Imai, H. (1994, January 6\u20138). Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based k-Clustering. Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, NY, USA.","key":"ref_13","DOI":"10.1145\/177424.178042"},{"doi-asserted-by":"crossref","unstructured":"Cohen, M., Elder, S., Musco, C., Musco, C., and Persu, M. (2015, January 14\u201317). Dimensionality reduction for k-means clustering and low rank approximation. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, Portland, OR, USA.","key":"ref_14","DOI":"10.1145\/2746539.2746569"},{"doi-asserted-by":"crossref","unstructured":"Becchetti, L., Bury, M., Cohen-Addad, V., Grandoni, F., and Schwiegelshohn, C. (2019, January 23\u201326). Oblivious dimension reduction for k-means: Beyond subspaces and the Johnson-Lindenstrauss lemma. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, USA.","key":"ref_15","DOI":"10.1145\/3313276.3316318"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","article-title":"Extensions of Lipschitz maps into a Hilbert space","volume":"26","author":"Lindenstrauss","year":"1984","journal-title":"Contemp. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00454-006-1271-x","article-title":"Smaller coresets for k-median and k-means clustering","volume":"37","author":"Kushal","year":"2007","journal-title":"Discret. Comput. Geom."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0031-3203(81)90009-1","article-title":"Generalizing the Hough transform to detect arbitrary shapes","volume":"13","author":"Ballard","year":"1981","journal-title":"Pattern Recognit."},{"unstructured":"Bhattacharya, A., and Jaiswal, R. (2017). On the k-means\/Median Cost Function. arXiv.","key":"ref_19"},{"unstructured":"Wilkinson, B., and Allen, M. (1999). Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, Prentice-Hall.","key":"ref_20"},{"doi-asserted-by":"crossref","unstructured":"Mahajan, M., Nimbhorkar, P., and Varadarajan, K. (2009). The planar k-means problem is NP-hard. WALCOM, Springer.","key":"ref_21","DOI":"10.1007\/978-3-642-00202-1_24"},{"unstructured":"Feldman, D., Volkov, M.V., and Rus, D. (2015). Dimensionality Reduction of Massive Sparse Datasets Using Coresets. arXiv.","key":"ref_22"},{"doi-asserted-by":"crossref","unstructured":"Fichtenberger, H., Gill\u00e9, M., Schmidt, M., Schwiegelshohn, C., and Sohler, C. (2013). BICO: BIRCH meets coresets for k-means clustering. European Symposium on Algorithms, Springer.","key":"ref_23","DOI":"10.1007\/978-3-642-40450-4_41"},{"key":"ref_24","first-page":"2.1","article-title":"StreamKM++ A clustering algorithm for data streams","volume":"17","author":"Ackermann","year":"2012","journal-title":"J. Exp. Algorithmics (JEA)"},{"unstructured":"LeCun, Y., and Cortes, C. (2020, March 10). The MNIST Database of Handwritten Digits. Available online: http:\/\/yann.lecun.com\/exdb\/mnist\/.","key":"ref_25"},{"unstructured":"Alimoglu, F., Doc, D., Alpaydin, E., and Denizhan, Y. (2020, March 10). Combining Multiple Classifiers for Pen-Based Handwritten Digit Recognition. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.25.6299&rep=rep1&type=pdf.","key":"ref_26"},{"unstructured":"LeCun, Y. (2020, March 10). Nips Online Web Site. Available online: http:\/\/nips.djvuzone.org.","key":"ref_27"},{"unstructured":"The Free Wikipedia (2017, February 01). Encyclopedia. Available online: https:\/\/dumps.wikimedia.org\/enwiki\/20170220\/.","key":"ref_28"},{"unstructured":"Rehurek, R., and Sojka, P. (2020, March 10). Gensim\u2014Statistical Semantics in Python. Available online: https:\/\/www.fi.muni.cz\/usr\/sojka\/posters\/rehurek-sojka-scipy2011.pdf.","key":"ref_29"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/4\/92\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:30:45Z","timestamp":1760362245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/4\/92"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,14]]},"references-count":29,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,4]]}},"alternative-id":["a13040092"],"URL":"https:\/\/doi.org\/10.3390\/a13040092","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,4,14]]}}}