{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T13:25:35Z","timestamp":1762608335458,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K00159"],"award-info":[{"award-number":["JP17K00159"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Data Sci Anal"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s41060-021-00270-4","type":"journal-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:02:17Z","timestamp":1623790937000},"page":"229-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["CPI-model-based analysis of sparse k-means clustering algorithms"],"prefix":"10.1007","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5578-842X","authenticated-orcid":false,"given":"Kazuo","family":"Aoyama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazumi","family":"Saito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tetsuo","family":"Ikeda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"270_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75, 245\u2013248 (2009)","journal-title":"Mach. Learn."},{"issue":"11","key":"270_CR2","doi-asserted-by":"publisher","first-page":"2773","DOI":"10.1587\/transinf.2017EDP7392","volume":"E101\u2013D","author":"K Aoyama","year":"2018","unstructured":"Aoyama, K., Saito, K., Ikeda, T.: Accelerating a Lloyd-type k-means clustering algorithm with summable lower bounds in a lower-dimensional space. IEICE Trans. Inf. Syst. E101\u2013D(11), 2773\u20132782 (2018)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"270_CR3","doi-asserted-by":"crossref","unstructured":"Bhimani, J., Leeser, M., Mi, N.: Accelerating K-means clustering with parallel implementations and GPU computing. In: Proceedings of IEEE High Performance Extreme Computing Conference (HPEC), pp. 233\u2013242 (2015)","DOI":"10.1109\/HPEC.2015.7322467"},{"volume-title":"Information Retrieval: Implementing and Evaluating Search Engines","year":"2010","key":"270_CR4","unstructured":"B\u00fcttcher, S., Clarke, C.L.A., Cormack, G.V. (eds.): Information Retrieval: Implementing and Evaluating Search Engines. The MIT Press, Cambridge (2010)"},{"key":"270_CR5","doi-asserted-by":"crossref","unstructured":"Broder, A., Garcia-Pueyo, L., Josifovski, V., Vassilvitskii, S., Venkatesan, S.: Scalable k-means by ranked retrieval. In: Proceedings of the ACM International Conference on Web Search and Data Mining (WSDM), pp. 233\u2013242 (2014)","DOI":"10.1145\/2556195.2556260"},{"issue":"1\u20132","key":"270_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1007612920971","volume":"42","author":"IS Dhillon","year":"2001","unstructured":"Dhillon, I.S., Modha, D.S.: Concept decompositions for large sparse text data using clustering. Mach. Learn. 42(1\u20132), 143\u2013175 (2001)","journal-title":"Mach. Learn."},{"key":"270_CR7","unstructured":"Ding, Y., Zhao, Y., Shen, X., Musuvathi, M., Mytkowicz, T.: Yinyang k-means: a drop-in replacement of the classic k-means with consistent speedup. In: Proceedings of the 32nd International Conference on Machine Learning (ICML), pp. 579\u2013587 (2015)"},{"key":"270_CR8","unstructured":"Drake, J., Hamerly, G.: Accelerated k-means with adaptive distance bounds. In: Proceedings of 5th NIPS Workshop on Optimization for Machine Learning (2012)"},{"key":"270_CR9","unstructured":"Dua, D., Taniskidou, E.K.: Bag of words data set (PubMed abstracts) in UCI machine learning repository (2017). http:\/\/archive.ics.uci.edu\/ml"},{"issue":"1","key":"270_CR10","first-page":"1.4:1","volume":"24","author":"S Edelkamp","year":"2019","unstructured":"Edelkamp, S., Wei\u00df, A.: BlockQuicksort: avoiding branch mispredictions in quicksort. ACM J. Exp. Algorithmics (JEA) 24(1), 1.4:1\u20131.4:22 (2019)","journal-title":"ACM J. Exp. Algorithmics (JEA)"},{"key":"270_CR11","unstructured":"Elkan, C.: Using the triangle inequality to accelerate k-means. In: Proceedings of 20th International Conference on Machine Learning (ICML), pp. 147\u2013153 (2003)"},{"issue":"11","key":"270_CR12","doi-asserted-by":"publisher","first-page":"1610","DOI":"10.1109\/5.964441","volume":"89","author":"M Evers","year":"2001","unstructured":"Evers, M., Yeh, T.Y.: Understanding branches and designing branch predictors for high-performance microprocessors. Proc. IEEE 89(11), 1610\u20131620 (2001)","journal-title":"Proc. IEEE"},{"key":"270_CR13","unstructured":"Eyerman, S., Smith, J.E., Eeckhout, L.: Characterizing the branch misprediction penalty. In: Proceedings of the International Symposium on Performance Analysis of Systems and Software (ISPASS), pp. 48\u201358 (2006)"},{"key":"270_CR14","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. ACM Trans. Algorithms 8(1,\u00a0article\u00a04) (2012)","DOI":"10.1145\/2071379.2071383"},{"issue":"1","key":"270_CR15","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s00778-006-0025-y","volume":"16","author":"A Ghoting","year":"2007","unstructured":"Ghoting, A., Buehrer, G., Parthasarathy, S., Kim, D., Nguyen, A., Chen, Y.K., Dubey, P.: Cache-conscious frequent pattern mining on modern and emerging processors. VLDB J. 16(1), 77\u201396 (2007)","journal-title":"VLDB J."},{"key":"270_CR16","doi-asserted-by":"crossref","unstructured":"Green, O., Dukhan, M., Vuduc, R.: Branch-avoiding graph algorithms. In: Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 212\u2013223 (2015)","DOI":"10.1145\/2755573.2755580"},{"key":"270_CR17","doi-asserted-by":"crossref","unstructured":"Hamerly, G.: Making k-means even faster. In: Proceedings SIAM International Conference on Data Mining (SDM), pp. 130\u2013140 (2010)","DOI":"10.1137\/1.9781611972801.12"},{"issue":"2","key":"270_CR18","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1109\/MM.2014.10","volume":"34","author":"P Hammarlund","year":"2014","unstructured":"Hammarlund, P., Martinez, A.J., Bajwa, A.A., Hill, D.L., Hallnor, E., Jiang, H., Dixon, M., Derr, M., Hunsaker, M., Kumar, R., Osborne, R.B., Rajwar, R., Singhal, R., D\u2019Sa, R., Chappell, R., Kaushik, S., Chennupaty, S., Jourdan, S., Gunther, S., Piazza, T., Burton, T.: Haswell: the fourth-generation Intel core processor. IEEE Micro 34(2), 6\u201320 (2014)","journal-title":"IEEE Micro"},{"key":"270_CR19","unstructured":"Harman, D., Fox, E., Baeza-Yates, R., Lee, W.: Inverted files. In: W.B. Frakes, R.\u00a0Baeza-Yates (eds.) Information Retrieval: Data Structures & Algorithms, chap.\u00a03, pp. 28\u201343. Prentice Hall, New Jersey (1992)"},{"key":"270_CR20","doi-asserted-by":"crossref","unstructured":"Hattori, T., Aoyama, K., Saito, K., Ikeda, T., Kobayashi, E.: Pivot-based k-means algorithm for numerous-class data sets. In: Proceedings of SIAM International Conference on Data Mining (SDM), pp. 333\u2013341 (2016)","DOI":"10.1137\/1.9781611974348.38"},{"volume-title":"Computer Architecture, Sixth Edition: A Quantitative Approach","year":"2017","key":"270_CR21","unstructured":"Hennessy, J.L., Patterson, D.A. (eds.): Computer Architecture, Sixth Edition: A Quantitative Approach. Morgan Kaufmann, San Mateo (2017)"},{"key":"270_CR22","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1007\/s11227-011-0672-7","volume":"64","author":"L Jian","year":"2013","unstructured":"Jian, L., Wang, C., Liu, Y., Liang, S., Yi, W., Shi, Y.: Parallel data mining techniques on graphics processing unit with compute unified device architecture (CUDA). J. Supercomput. 64, 942\u2013967 (2013)","journal-title":"J. Supercomput."},{"issue":"6","key":"270_CR23","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1109\/TC.2017.2780239","volume":"67","author":"R Jongerius","year":"2018","unstructured":"Jongerius, R., Anghel, A., Dittmann, G., Mariani, G., Vermij, E., Corporaal, H.: Analytic multi-core processor model for fast design-space exploration. IEEE Trans. Comput. 67(6), 755\u2013770 (2018)","journal-title":"IEEE Trans. Comput."},{"issue":"6245","key":"270_CR24","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1126\/science.aaa8415","volume":"349","author":"MI Jordan","year":"2015","unstructured":"Jordan, M.I., Mitchell, T.M.: Machine learning: trends, perspectives, and prospects. Science 349(6245), 255\u2013260 (2015)","journal-title":"Science"},{"key":"270_CR25","first-page":"780","volume-title":"Algorithms-ESA2006. Lecture Notes in Computer Science","author":"K Kaligosi","year":"2006","unstructured":"Kaligosi, K., Sanders, P.: How branch mispredictions affect quicksort. In: Azar, Y., Erlebach, T. (eds.) Algorithms-ESA2006. Lecture Notes in Computer Science, pp. 780\u2013791. Springer, Berlin (2006)"},{"key":"270_CR26","unstructured":"Knuth, D.E.: Retrieval on secondary keys. In: The Art of Computer Programming: Volume 3: Sorting and Searching, chap. 5.2.4 and 6.5. Addison-Wesley Professional (1998)"},{"key":"270_CR27","series-title":"Lecture Notes in Computer Science, chap. 10","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-36574-5_10","volume-title":"Algorithms for Memory Hierarchies","author":"M Kowarschik","year":"2003","unstructured":"Kowarschik, M., Wei\u00df, C.: An overview of cache optimization techniques and cache-aware numerical algorithms. In: Meyer, U., Sanders, P., Sibeyn, J. (eds.) Algorithms for Memory Hierarchies. Lecture Notes in Computer Science, chap. 10, pp. 213\u2013232. Springer, Berlin (2003)"},{"issue":"2","key":"270_CR28","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"SP Lloyd","year":"1982","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129\u2013137 (1982)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"270_CR29","unstructured":"MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, pp. 281\u2013297 (1967)"},{"key":"270_CR30","unstructured":"Intel Corp.: Disclosure of hardware prefetcher control on some Intel processors (2014). https:\/\/software.intel.com\/en-us\/articles\/disclosure-of-hw-prefetcher-control-on-some-intel-processors"},{"key":"270_CR31","unstructured":"Intel Corp.: Intel memory latency checker v3.9 (2020). https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/articles\/intelr-memory-latency-checker.html"},{"key":"270_CR32","unstructured":"Newling, J., Fleuret, F.: Fast k-means with accurate bounds. In: Proceedings of 33rd International Conference on Machine Learning (ICML) (2016)"},{"key":"270_CR33","doi-asserted-by":"crossref","unstructured":"Perdacher, M., Plant, C., B\u00f6hm, C.: Cache-oblivious high-performance similarity join. In: Proceedings of International Conference on Management of Data (SIGMOD), pp. 87\u2013104 (2019)","DOI":"10.1145\/3299869.3319859"},{"key":"270_CR34","unstructured":"Perf: Linux profiling with performance counters (2019). https:\/\/perf.wiki.kernel.org\/index.php"},{"volume-title":"Foundations of Multidimensional and Metric Data Structures","year":"2006","key":"270_CR35","unstructured":"Samet, H. (ed.): Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers Inc., San Francisco (2006)"},{"key":"270_CR36","doi-asserted-by":"crossref","unstructured":"Sivic, J., Zisserman, A.: Video Google: a text retrieval approach to object matching in videos. In: Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 1470\u20131478 (2003)","DOI":"10.1109\/ICCV.2003.1238663"},{"issue":"1","key":"270_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-007-0114-2","volume":"14","author":"X Wu","year":"2008","unstructured":"Wu, X., Kumar, V., Quinlan, J.R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G.J., Ng, A., Liu, B., Yu, P.S., Zhou, Z.H., Steinbach, M., Hand, D.J., Steinberg, D.: Top 10 algorithms in data mining. Knowl. Inf. Syst. 14(1), 1\u201337 (2008)","journal-title":"Knowl. Inf. Syst."},{"key":"270_CR38","doi-asserted-by":"crossref","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search. ACM Comput. Surv. 38(2,\u00a0article\u00a06) (2006)","DOI":"10.1145\/1132956.1132959"}],"container-title":["International Journal of Data Science and Analytics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41060-021-00270-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41060-021-00270-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41060-021-00270-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,22]],"date-time":"2021-08-22T05:25:19Z","timestamp":1629609919000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41060-021-00270-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["270"],"URL":"https:\/\/doi.org\/10.1007\/s41060-021-00270-4","relation":{},"ISSN":["2364-415X","2364-4168"],"issn-type":[{"type":"print","value":"2364-415X"},{"type":"electronic","value":"2364-4168"}],"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}