{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T07:11:25Z","timestamp":1760339485853,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031962387"},{"type":"electronic","value":"9783031962394"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-96239-4_8","type":"book-chapter","created":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T02:03:11Z","timestamp":1750471391000},"page":"101-118","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight Bounds for\u00a0an\u00a0Accelerated $$k$$-means$$++$$ Algorithm"],"prefix":"10.1007","author":[{"given":"Guillem","family":"Rodr\u00edguez-Corominas","sequence":"first","affiliation":[]},{"given":"Maria J.","family":"Blesa","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Blum","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,22]]},"reference":[{"unstructured":"Yahoo! Webscope Dataset ydata-frontpage-todaymodule-clicks-v1_0","key":"8_CR1"},{"unstructured":"Anagnostopoulos, C.: Query Analytics Workloads Dataset (2018). UCI Machine Learning Repository","key":"8_CR2"},{"unstructured":"Arthur, D., Vassilvitskii, S.: K-means++: the advantages of careful seeding. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201907), pp. 1027\u20131035. Society for Industrial and Applied Mathematics (SIAM) (2007)","key":"8_CR3"},{"doi-asserted-by":"publisher","unstructured":"Baldi, P., Sadowski, P., Whiteson, D.: Searching for exotic particles in high-energy physics with deep learning. Nat. Commun. 5(1) (2014). Springer Science and Business Media LLC. https:\/\/doi.org\/10.1007\/978-3-031-25091-0","key":"8_CR4","DOI":"10.1007\/978-3-031-25091-0"},{"unstructured":"Bertin-Mahieux, T.: Year Prediction MSD Dataset (2011). UCI Machine Learning Repository","key":"8_CR5"},{"unstructured":"Bertin-Mahieux, T., Ellis, D.P., Whitman, B., Lamere, P.: The million song dataset. In: Proceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011) (2011)","key":"8_CR6"},{"unstructured":"Bhatt, R., Dhall, A.: Skin Segmentation Dataset (2009). UCI Machine Learning Repository","key":"8_CR7"},{"unstructured":"Bock, R.: MAGIC Gamma Telescope Dataset (2004). UCI Machine Learning Repository","key":"8_CR8"},{"doi-asserted-by":"crossref","unstructured":"Caruana, R., Joachims, T., Backstrom, L.: KDD-Cup 2004: results and analysis. In: ACM SIGKDD Explorations Newsletter 6(2), 95\u2013108 (2004). Association for Computing Machinery (ACM)","key":"8_CR9","DOI":"10.1145\/1046456.1046470"},{"unstructured":"Corominas, G.R., Blesa, M.J., Blum, C.: Accelerating the k-means++ algorithm by using geometric information (2024). https:\/\/arxiv.org\/abs\/2408.13189","key":"8_CR10"},{"unstructured":"Dau, H.A., et al.: Hexagon-ML: The UCR Time Series Classification Archive (2018)","key":"8_CR11"},{"unstructured":"Drake, J., Hamerly, G.: Accelerated k-means with adaptive distance bounds. In: 5th NIPS Workshop on Optimization for Machine Learning, vol.\u00a08, pp.\u00a01\u20134 (2012)","key":"8_CR12"},{"unstructured":"Elkan, C.: Using the triangle inequality to accelerate k-means. In: Proceedings of the 20th International Conference on International Conference on Machine Learning (ICML\u201903), pp. 147\u2013153. AAAI Press (2003)","key":"8_CR13"},{"unstructured":"Fonollosa, J.: Gas Sensor Array Under Dynamic Gas Mixtures Dataset (2015). UCI Machine Learning Repository","key":"8_CR14"},{"doi-asserted-by":"crossref","unstructured":"Fonollosa, J., Sheik, S., Huerta, R., Marco, S.: Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sens. Actuators B: Chem. 215, 618\u2013629 (2015). Elsevier BV","key":"8_CR15","DOI":"10.1016\/j.snb.2015.03.028"},{"doi-asserted-by":"crossref","unstructured":"Fr\u00e4nti, P., Sieranoja, S.: How much can k-means be improved by using better initialization and repeats? Pattern Recogn. 93, 95\u2013112 (2019). Elsevier BV","key":"8_CR16","DOI":"10.1016\/j.patcog.2019.04.014"},{"doi-asserted-by":"crossref","unstructured":"Govender, P., Sivakumar, V.: Application of k-means and hierarchical clustering techniques for analysis of air pollution: a review (1980\u20132019). Atmos. Pollut. Res. 11(1), 40\u201356 (2020)","key":"8_CR17","DOI":"10.1016\/j.apr.2019.09.009"},{"doi-asserted-by":"crossref","unstructured":"Hamerly, G.: Making k-means even faster. In: Proceedings of the 2010 SIAM International Conference on Data Mining (SDM), pp. 130\u2013140. Society for Industrial and Applied Mathematics (SIAM) (2010)","key":"8_CR18","DOI":"10.1137\/1.9781611972801.12"},{"doi-asserted-by":"publisher","unstructured":"Hamerly, G., Drake, J.: Accelerating Lloyd\u2019s algorithm for k-means clustering. In: Celebi, M. (eds) Partitional Clustering Algorithms, pp. 41\u201378. Springer International Publishing (2014). https:\/\/doi.org\/10.1007\/978-3-319-09259-1_2","key":"8_CR19","DOI":"10.1007\/978-3-319-09259-1_2"},{"unstructured":"Hebrail, G., Berard, A.: Individual Household Electric Power Consumption Dataset (2006). UCI Machine Learning Repository","key":"8_CR20"},{"unstructured":"Heck, D., Knapp, J., Capdevielle, J.N., Schatz, G., Thouw, T.: CORSIKA: a Monte Carlo code to simulate extensive air showers. Forschungszentrum Karlsruhe (1998)","key":"8_CR21"},{"doi-asserted-by":"crossref","unstructured":"Ikotun, A.M., Ezugwu, A.E., Abualigah, L., Abuhaija, B., Heming, J.: K-means clustering algorithms: a comprehensive review, variants analysis, and advances in the era of big data. Inf. Sci. 622, 178\u2013210 (2023). Elsevier BV","key":"8_CR22","DOI":"10.1016\/j.ins.2022.11.139"},{"unstructured":"Kaul, M.: 3D Road Network Dataset (2013). UCI Machine Learning Repository","key":"8_CR23"},{"doi-asserted-by":"crossref","unstructured":"Kaul, M., Yang, B., Jensen, C.S.: Building accurate 3D spatial networks to enable next generation intelligent transportation systems. In: IEEE 14th International Conference on Mobile Data Management. Institute of Electrical and Electronics Engineers (IEEE) (2013)","key":"8_CR24","DOI":"10.1109\/MDM.2013.24"},{"unstructured":"Krizhevsky, A.: Learning Multiple Layers of Features from Tiny Images. University of Toronto (2009)","key":"8_CR25"},{"doi-asserted-by":"crossref","unstructured":"Lecun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proceedings of the IEEE 86(11), 2278\u20132324 (1998). Institute of Electrical and Electronics Engineers (IEEE)","key":"8_CR26","DOI":"10.1109\/5.726791"},{"unstructured":"Logacjov, A., Ustad, A.: HAR70+ Dataset (2023). UCI Machine Learning Repository","key":"8_CR27"},{"unstructured":"Newling, J., Fleuret, F.: Fast k-means with accurate bounds. In: Proceedings of the 33rd International Conference on Machine Learning (ICML\u201916), vol.\u00a048, pp. 936\u2013944. PMLR (2016)","key":"8_CR28"},{"unstructured":"Ortega-Binderberger, M.: Corel Image Features Dataset (1998). UCI Machine Learning Repository","key":"8_CR29"},{"doi-asserted-by":"crossref","unstructured":"Pan, H., Lei, Y., Yin, S.: K-means clustering algorithm for data distribution in cloud computing environment. Int. J. Grid Util. Comput. 12(3), 322 (2021)","key":"8_CR30","DOI":"10.1504\/IJGUC.2021.117873"},{"doi-asserted-by":"crossref","unstructured":"Rodriguez-Lujan, I., Fonollosa, J., Vergara, A., Homer, M., Huerta, R.: On the calibration of sensor arrays for pattern recognition using the minimal number of experiments. Chemometrics Intell. Lab. Syst. 130, 123\u2013134 (2014), Elsevier BV","key":"8_CR31","DOI":"10.1016\/j.chemolab.2013.10.012"},{"doi-asserted-by":"crossref","unstructured":"Ry\u0161av\u00fd, P., Hamerly, G.: Geometric methods to accelerate k-means algorithms. In: Proceedings of the 2016 SIAM International Conference on Data Mining (SDM). pp. 324\u2013332. Society for Industrial and Applied Mathematics (SIAM) (2016)","key":"8_CR32","DOI":"10.1137\/1.9781611974348.37"},{"doi-asserted-by":"crossref","unstructured":"Tan, C.W., Webb, G.I., Petitjean, F.: Indexing and classifying gigabytes of time series under time warping. In: Proceedings of the 2017 SIAM International Conference on Data Mining (SDM), pp. 282\u2013290. Society for Industrial and Applied Mathematics (SIAM) (2017)","key":"8_CR33","DOI":"10.1137\/1.9781611974973.32"},{"doi-asserted-by":"crossref","unstructured":"Ustad, A., et al.: Validation of an activity type recognition model classifying daily physical behavior in older adults: the HAR70+ model. Sensors 23(5), \u00a02368 (2023). MDPI","key":"8_CR34","DOI":"10.3390\/s23052368"},{"doi-asserted-by":"crossref","unstructured":"Uzilov, A.V., Keegan, J.M., Mathews, D.H.: Detection of non-coding RNAs on the basis of predicted secondary structure formation free energy change. BMC Bioinformatics 7(1) (2006). Springer Science and Business Media LLC","key":"8_CR35","DOI":"10.1186\/1471-2105-7-173"},{"unstructured":"Vergara, A.: Gas Sensor Array Drift Dataset (2012). UCI Machine Learning Repository","key":"8_CR36"},{"doi-asserted-by":"crossref","unstructured":"Vergara, A., Vembu, S., Ayhan, T., Ryan, M.A., Homer, M.L., Huerta, R.: Chemical gas sensor drift compensation using classifier ensembles. Sens. Actuators B: Chem. 166\u2013167, 320\u2013329 (2012). Elsevier BV","key":"8_CR37","DOI":"10.1016\/j.snb.2012.01.074"},{"unstructured":"Whiteson, D.: SUSY Dataset (2014). UCI Machine Learning Repository","key":"8_CR38"},{"doi-asserted-by":"crossref","unstructured":"Wu, X., et al.: Top 10 algorithms in data mining. Knowl. Inf. Syst. 14(1), 1\u201337 (2007). Springer Science and Business Media LLC","key":"8_CR39","DOI":"10.1007\/s10115-007-0114-2"}],"container-title":["IFIP Advances in Information and Communication Technology","Artificial Intelligence Applications and Innovations"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-96239-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T06:37:54Z","timestamp":1760337474000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-96239-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031962387","9783031962394"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-96239-4_8","relation":{},"ISSN":["1868-4238","1868-422X"],"issn-type":[{"type":"print","value":"1868-4238"},{"type":"electronic","value":"1868-422X"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AIAI","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"IFIP International Conference on Artificial Intelligence Applications and Innovations","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Limassol","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aiai2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ifipaiai.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}