{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T13:17:25Z","timestamp":1772803045929,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,4,14]],"date-time":"2021-04-14T00:00:00Z","timestamp":1618358400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,14]],"date-time":"2021-04-14T00:00:00Z","timestamp":1618358400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s10994-021-05965-0","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T06:28:47Z","timestamp":1618468127000},"page":"881-905","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["QuicK-means: accelerating inference for K-means by learning fast transforms"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6645-5233","authenticated-orcid":false,"given":"Luc","family":"Giffon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentin","family":"Emiya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hachem","family":"Kadri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liva","family":"Ralaivola","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,14]]},"reference":[{"key":"5965_CR1","unstructured":"Ailon, N., Leibovich, O., & Nair, V. (2020). Sparse linear networks with a fixed butterfly structure: Theory and practice. arXiv preprint arXiv:200708864."},{"key":"5965_CR2","unstructured":"Arthur, D., & Vassilvitskii, S. (2006). k-means++: The advantages of careful seeding. Technical reports, Stanford."},{"issue":"1\u20132","key":"5965_CR3","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10107-013-0701-9","volume":"146","author":"J Bolte","year":"2014","unstructured":"Bolte, J., Sabach, S., & Teboulle, M. (2014). Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Mathematical Programming, 146(1\u20132), 459\u2013494.","journal-title":"Mathematical Programming"},{"issue":"2","key":"5965_CR4","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1109\/TIT.2014.2375327","volume":"61","author":"C Boutsidis","year":"2014","unstructured":"Boutsidis, C., Zouzias, A., Mahoney, M. W., & Drineas, P. (2014). Randomized dimensionality reduction for $$k$$-means clustering. IEEE Transactions on Information Theory, 61(2), 1045\u20131062.","journal-title":"IEEE Transactions on Information Theory"},{"key":"5965_CR5","unstructured":"Dao, T., Gu, A., Eichhorn, M., Rudra, A., & Re, C. (2019). Learning fast algorithms for linear transforms using butterfly factorizations. In International conference on machine learning (pp. 1517\u20131527)."},{"key":"5965_CR6","unstructured":"Dua, D., & Graff, C. (2017). UCI machine learning repository. http:\/\/archive.ics.uci.edu\/ml."},{"key":"5965_CR7","unstructured":"Elkan, C. (2003). Using the triangle inequality to accelerate k-means. In Proceedings of the 20th international conference on machine learning (ICML-03) (pp. 147\u2013153)"},{"key":"5965_CR8","unstructured":"Griffin, G., Holub, A., & Perona, P. (2007). The caltech-256. Caltech technical report (p. 1)."},{"key":"5965_CR9","doi-asserted-by":"crossref","unstructured":"Hamerly, G. (2010). Making k-means even faster. In Proceedings of the SIAM international conference on data mining (pp. 130\u2013140). SIAM","DOI":"10.1137\/1.9781611972801.12"},{"issue":"1","key":"5965_CR10","first-page":"100","volume":"28","author":"JA Hartigan","year":"1979","unstructured":"Hartigan, J. A., & Wong, M. A. (1979). Algorithm as 136: A k-means clustering algorithm. Journal of the Royal Statistical Society Series C (Applied Statistics), 28(1), 100\u2013108.","journal-title":"Journal of the Royal Statistical Society Series C (Applied Statistics)"},{"issue":"8","key":"5965_CR11","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","volume":"31","author":"AK Jain","year":"2010","unstructured":"Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 31(8), 651\u2013666.","journal-title":"Pattern Recognition Letters"},{"key":"5965_CR12","doi-asserted-by":"crossref","unstructured":"Keriven, N., Tremblay, N., Traonmilin, Y., & Gribonval, R. (2017). Compressive k-means. In International conference on acoustics speech and signal processing (ICASSP) (pp. 6369\u20136373). IEEE.","DOI":"10.1109\/ICASSP.2017.7953382"},{"key":"5965_CR13","first-page":"981","volume":"13","author":"S Kumar","year":"2012","unstructured":"Kumar, S., Mohri, M., & Talwalkar, A. (2012). Sampling methods for the nystr\u00f6m method. Journal of Machine Learning Research, 13, 981\u20131006.","journal-title":"Journal of Machine Learning Research"},{"key":"5965_CR14","unstructured":"Le, Q., Sarl\u00f3s, T., & Smola, A. (2013). Fastfood-approximating kernel expansions in loglinear time. In International conference on machine learning"},{"issue":"4","key":"5965_CR15","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1109\/JSTSP.2016.2543461","volume":"10","author":"L Le Magoarou","year":"2016","unstructured":"Le Magoarou, L., & Gribonval, R. (2016). Flexible multilayer sparse approximations of matrices and applications. IEEE Journal of Selected Topics in Signal Processing, 10(4), 688\u2013700.","journal-title":"IEEE Journal of Selected Topics in Signal Processing"},{"key":"5965_CR16","unstructured":"LeCun, Y., Cortes, C., & Burges, C. (2010). Mnist handwritten digit database. http:\/\/yannlecuncom\/exdb\/mnist7:23."},{"issue":"2","key":"5965_CR17","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1137\/15M1007173","volume":"13","author":"Y Li","year":"2015","unstructured":"Li, Y., Yang, H., Martin, E. R., Ho, K. L., & Ying, L. (2015). Butterfly factorization. Multiscale Modeling & Simulation, 13(2), 714\u2013732.","journal-title":"Multiscale Modeling & Simulation"},{"key":"5965_CR18","doi-asserted-by":"crossref","unstructured":"Liu, W., Shen, X., & Tsang, I. (2017). Sparse embedded $$k$$-means clustering. In Advances in neural information processing systems (pp. 3319\u20133327)","DOI":"10.1007\/978-3-319-70139-4"},{"issue":"2","key":"5965_CR19","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1145\/321879.321881","volume":"22","author":"J Morgenstern","year":"1975","unstructured":"Morgenstern, J. (1975). The linear complexity of computation. Journal of the ACM, 22(2), 184\u2013194.","journal-title":"Journal of the ACM"},{"issue":"11","key":"5965_CR20","doi-asserted-by":"publisher","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","volume":"36","author":"M Muja","year":"2014","unstructured":"Muja, M., & Lowe, D. G. (2014). Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(11), 2227\u20132240.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"5965_CR21","unstructured":"Musco, C., & Musco, C. (2017) Recursive sampling for the nystr\u00f6m method. In Advances in neural information processing systems(pp. 3833\u20133845)."},{"key":"5965_CR22","unstructured":"Nene, S. A., Nayar, S. K., & Murase, H. (1996). Columbia object image library (coil-20). Technical reports."},{"key":"5965_CR23","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., et al. (2011). Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12, 2825\u20132830.","journal-title":"Journal of Machine Learning Research"},{"key":"5965_CR24","unstructured":"Que, Q., & Belkin, M. (2016). Back to the future: Radial basis function networks revisited. In Artificial intelligence and statistics (pp. 1375\u20131383)."},{"key":"5965_CR25","doi-asserted-by":"crossref","unstructured":"Sculley, D. (2010). Web-scale k-means clustering. In Proceedings of the 19th international conference on World wide web (pp. 1177\u20131178). ACM","DOI":"10.1145\/1772690.1772862"},{"key":"5965_CR26","doi-asserted-by":"crossref","unstructured":"Shen, X., Liu, W., Tsang, I., Shen, F., & Sun, Q. S. (2017). Compressed k-means for large-scale clustering. In Thirty-first AAAI conference on artificial intelligence","DOI":"10.1609\/aaai.v31i1.10852"},{"key":"5965_CR27","unstructured":"Si, S., Hsieh, C. J., & Dhillon, I. (2016). Computationally efficient nystr\u00f6m approximation using fast transforms. In International conference on machine learning (pp. 2655\u20132663)"},{"key":"5965_CR28","unstructured":"Vahid, K. A., Prabhu, A., Farhadi, A., & Rastegari, M. (2020). Butterfly transform: an efficient FFT based neural architecture design. In Proceedings of the IEEE\/CVF conference on computer vision and pattern recognition"},{"issue":"1","key":"5965_CR29","first-page":"5148","volume":"17","author":"T Van Laarhoven","year":"2016","unstructured":"Van Laarhoven, T., & Marchiori, E. (2016). Local network community detection with continuous optimization of conductance and weighted kernel k-means. The Journal of Machine Learning Research, 17(1), 5148\u20135175.","journal-title":"The Journal of Machine Learning Research"},{"key":"5965_CR30","first-page":"2837","volume":"11","author":"NX Vinh","year":"2010","unstructured":"Vinh, N. X., Epps, J., & Bailey, J. (2010). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. The Journal of Machine Learning Research, 11, 2837\u20132854.","journal-title":"The Journal of Machine Learning Research"},{"key":"5965_CR31","unstructured":"Williams, C. K., & Seeger, M. (2001). Using the nystr\u00f6m method to speed up kernel machines. In Advances in neural information processing systems (pp. 682\u2013688)."},{"key":"5965_CR32","unstructured":"Xiao, H., Rasul, K., & Vollgraf, R. (2017). Fashion-mnist: A novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:170807747."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-05965-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-05965-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-05965-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T09:45:46Z","timestamp":1671875146000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-05965-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,14]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["5965"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-05965-0","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,14]]},"assertion":[{"value":"20 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}