{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T11:28:40Z","timestamp":1764588520182,"version":"3.44.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["22H03596"],"award-info":[{"award-number":["22H03596"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>K-Multiple-Means is an extension of K-means for the clustering of multiple means used in many applications, such as image segmentation, load balancing, and blind-source separation. Since K-means uses only one mean to represent each cluster, it fails to capture non-spherical cluster structures of data points. However, since K-Multiple-Means represents the cluster by computing multiple means and grouping them into specified c clusters, it can effectively capture the non-spherical clusters of the data points. To obtain the clusters, K-Multiple-Means updates a similarity matrix of a bipartite graph between the data points and the multiple means by iteratively computing the leading c singular vectors of the matrix. K-Multiple-Means, however, incurs a high computation cost for large-scale data due to the iterative SVD computations. Our proposal, F-KMM, increases the efficiency of K-Multiple-Means by computing the singular vectors from a smaller similarity matrix between the multiple means obtained from the similarity matrix of the bipartite graph. To compute the similarity matrix of the bipartite graph efficiently, we skip unnecessary distance computations and estimate lower bounding distances between the data points and the multiple means. Theoretically, the proposed approach guarantees the same clustering results as K-Multiple-Means since it can exactly compute the singular vectors from the similarity matrix between the multiple means. Experiments show that our approach is several orders of magnitude faster than previous clustering approaches that use multiple means.<\/jats:p>","DOI":"10.1145\/3639273","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Algorithm for K-Multiple-Means"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-1118","authenticated-orcid":false,"given":"Yasuhiro","family":"Fujiwara","sequence":"first","affiliation":[{"name":"NTT Communication Science Laboratories, Atsugi-shi, Kanagawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2915-4615","authenticated-orcid":false,"given":"Atsutoshi","family":"Kumagai","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, Musashino-shi, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4279-9503","authenticated-orcid":false,"given":"Yasutoshi","family":"Ida","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, Musashino-shi, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9378-0099","authenticated-orcid":false,"given":"Masahiro","family":"Nakano","sequence":"additional","affiliation":[{"name":"NTT Communication Science Laboratories, Atsugi-shi, Kanagawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2181-0056","authenticated-orcid":false,"given":"Makoto","family":"Nakatsuji","sequence":"additional","affiliation":[{"name":"NTT Human Informatics Laboratories, Yokosuka-shi, Kanagawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3042-6810","authenticated-orcid":false,"given":"Akisato","family":"Kimura","sequence":"additional","affiliation":[{"name":"NTT Communication Science Laboratories, Atsugi-shi, Kanagawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"David Arthur and Sergei Vassilvitskii. 2007. k-means: The Advantages of Careful Seeding. In SODA. 1027--1035."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Shenglan Ben Zhong Jin and Jingyu Yang. 2011. Guided Fuzzy Clustering with Multi-prototypes. In IJCNN. 2430--2436.","DOI":"10.1109\/IJCNN.2011.6033534"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.118862"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335388"},{"volume-title":"Spectral Graph Theory","author":"Chung Fan R. K.","key":"e_1_2_1_5_1","unstructured":"Fan R. K. Chung. 1996. Spectral Graph Theory. American Mathematical Society."},{"volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_6_1","unstructured":"Thomas H. Cormen, Charles E. Leiserson Ronald L. Rivest, and Clifford Stein. 2022. Introduction to Algorithms. The MIT Press."},{"key":"e_1_2_1_7_1","unstructured":"James W. Demmel. 2017. Applied Numerical Linear Algebra. Orient Blackswan."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014118"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1115"},{"key":"e_1_2_1_10_1","volume-title":"J\u00f6 rg Sander, and Xiaowei Xu","author":"Ester Martin","year":"1996","unstructured":"Martin Ester, Hans-Peter Kriegel, J\u00f6 rg Sander, and Xiaowei Xu. 1996. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD. 226--231."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.35.11.652"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021938"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735498"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Yasuhiro Fujiwara Makoto Nakatsuji Hiroaki Shiokawa Yasutoshi Ida and Machiko Toyoda. 2015. Adaptive Message Update for Fast Affinity Propagation. In KDD. ACM 309--318.","DOI":"10.1145\/2783258.2783280"},{"key":"e_1_2_1_15_1","unstructured":"Kinsuk Giri and Tuhin Biswas. 2022. Applications of Computational Geometry in Clustering: A Review. 209--214."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2002.1000150"},{"volume-title":"Scaling A Blockchain System For 5G-based Vehicular Networks Using Heuristic Sharding","author":"Gu Pengwenlong","key":"e_1_2_1_17_1","unstructured":"Pengwenlong Gu, Dingjie Zhong, Cunqing Hua, Farid Na\"i t-Abdesselam, Ahmed Serhrouchni, and Rida Khatoun. 2021. Scaling A Blockchain System For 5G-based Vehicular Networks Using Heuristic Sharding. In GLOBECOM. IEEE, 1--6."},{"volume-title":"Matrix Algebra From a Statistician's Perspective","author":"Harville David A.","key":"e_1_2_1_18_1","unstructured":"David A. Harville. 2008. Matrix Algebra From a Statistician's Perspective. Springer."},{"key":"e_1_2_1_19_1","first-page":"68","article-title":"Chameleon","volume":"32","author":"Karypis G.","year":"1999","unstructured":"G. Karypis, Eui-Hong Han, and V. Kumar. 1999. Chameleon: Hierarchical Clustering Using Dynamic Modeling. Computer, Vol. 32, 8 (1999), 68--75.","journal-title":"Hierarchical Clustering Using Dynamic Modeling. Computer"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2021.3105196"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TFUZZ.2011.2182354"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(02)00060-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.09.015"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ting Luo Caiming Zhong Hong Li and Xia Sun. 2010. A Multi-prototype Clustering Algorithm Based on Minimum Spanning Tree. In FSKD. 1602--1607.","DOI":"10.1109\/FSKD.2010.5569359"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00034-020-01629-x"},{"key":"e_1_2_1_26_1","volume-title":"Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability","volume":"1","author":"MacQueen J. B.","year":"1967","unstructured":"J. B. MacQueen. 1967. Some Methods for Classification and Analysis of MultiVariate Observations. In Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1. University of California Press, 281--297."},{"volume-title":"Introduction to Information Retrieval","author":"Manning Christopher D.","key":"e_1_2_1_27_1","unstructured":"Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schuetze. 2008. Introduction to Information Retrieval. Cambridge University Press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"e_1_2_1_29_1","unstructured":"Andrew Y. Ng Michael I. Jordan and Yair Weiss. 2001. On Spectral Clustering: Analysis and an Algorithm. In NIPS. 849--856."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Feiping Nie Cheng-Long Wang and Xuelong Li. 2019. K-Multiple-Means: A Multiple-Means Clustering Method with Specified K Clusters. In SIGKDD. 959--967.","DOI":"10.1145\/3292500.3330846"},{"key":"e_1_2_1_31_1","unstructured":"Feiping Nie Xiaoqian Wang Cheng Deng and Heng Huang. 2017. Learning A Structured Optimal Bipartite Graph for Co-Clustering. In NIPS. 4129--4138."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Feiping Nie Xiaoqian Wang and Heng Huang. 2014. Clustering and Projected Clustering with Adaptive Neighbors. In KDD. 977--986.","DOI":"10.1145\/2623330.2623726"},{"key":"e_1_2_1_33_1","unstructured":"Feiping Nie Xiaoqian Wang Michael I. Jordan and Heng Huang. 2016. The Constrained Laplacian Rank Algorithm for Graph-Based Clustering. In AAAI. 1969--1976."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009745219419"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976698300017467"},{"volume-title":"High Performance Discovery In Time Series: Techniques And Case Studies","author":"Shasha Dennis","key":"e_1_2_1_36_1","unstructured":"Dennis Shasha and Yunyue Zhu. 2004. High Performance Discovery In Time Series: Techniques And Case Studies. SpringerVerlag."},{"key":"e_1_2_1_37_1","volume-title":"Mavris","author":"Sheridan Kevin","year":"2020","unstructured":"Kevin Sheridan, Tejas G. Puranik, Eugene Mangortey, Olivia J. Pinon-Fischer, Michelle Kirby, and Dimitri N. Mavris. 2020. An Application of DBSCAN Clustering for Flight Anomaly Detection During the Approach Phase."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"volume-title":"The Cauchy-Schwarz Master Class","author":"Steele J. Michael","key":"e_1_2_1_39_1","unstructured":"J. Michael Steele. 2004. The Cauchy-Schwarz Master Class. Cambridge University Press."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-0114(01)00191-9"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.28"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Chang-Dong Wang Jian-Huang Lai and Jun-Yong Zhu. 2010. A Conscience On-line Learning Approach for Kernel-Based Clustering. In ICDM. 531--540.","DOI":"10.1109\/ICDM.2010.57"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Lu Wang Huidong Wang and Chuanzheng Bai. 2021. A New Multi-Prototype Based Clustering Algorithm. In ICIST. 598--603.","DOI":"10.1109\/ICIST52614.2021.9440589"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2015.2495268"},{"volume-title":"Fundamentals of Matrix Computations","author":"Watkins David S.","key":"e_1_2_1_46_1","unstructured":"David S. Watkins. 2010. Fundamentals of Matrix Computations. Wiley."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/1869\/1\/012077"},{"key":"e_1_2_1_48_1","unstructured":"Jinglin Xu Junwei Han Kai Xiong and Feiping Nie. 2016. Robust and Sparse Fuzzy K-Means Clustering. In IJCAI. 2224--2230."},{"key":"e_1_2_1_49_1","unstructured":"Lihi Zelnik-Manor and Pietro Perona. 2004. Self-Tuning Spectral Clustering. In NIPS. 1601--1608."},{"key":"e_1_2_1_50_1","volume-title":"Simon","author":"Zha Hongyuan","year":"2001","unstructured":"Hongyuan Zha, Xiaofeng He, Chris H. Q. Ding, Ming Gu, and Horst D. Simon. 2001. Spectral Relaxation for K-means Clustering. In NIPS. 1057--1064."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Jingyuan Zhang. 2022. A New K-Multiple-Means Clustering Method. In KSEM. 621--632.","DOI":"10.1007\/978-3-031-10986-7_50"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.3390\/pr8020157"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639273","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:14:03Z","timestamp":1755789243000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639273"],"URL":"https:\/\/doi.org\/10.1145\/3639273","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}