{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T12:01:03Z","timestamp":1775476863795,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>\n            Balanced\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -means ensures representative centroids by forming equal-sized clusters, but struggles with slow clustering of massive distributed attributes and data-sharing restrictions. A common approach is adapting it to a vertical federated learning (VFL) framework, preventing raw data exposure by only intermediate result exchange and accelerating clustering via parallelism, yet it remains unexplored. In this paper, we propose a time-efficient, federated, and balanced\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -means algorithm, called Teb-means, to bridge the gap. We first formulate the balanced\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -means problem as a trace maximization problem (TMP) and propose an efficient coordinate-wise optimization (CO) scheme to solve it. We then integrate TMP and CO into the VFL framework by demonstrating that TMP can be decomposed into multiple subproblems based on each party's data, which can be solved using CO while exchanging only intermediate results. Notably, we build a trade-off between utility and communication efficiency by designing a greedy block-based strategy for CO (GBCO). Our theoretical analysis shows that Teb-means achieves linear time complexity on each client, and our communication round is constant in the mild condition. Experiments show that Teb-means is on average 12.18\u00d7 faster than other balanced clustering algorithms that can be federated, while achieving better balance without disrupting the cluster structure.\n          <\/jats:p>","DOI":"10.14778\/3749646.3749673","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4032-4044","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Federated and Balanced Clustering for High-Dimensional Data"],"prefix":"10.14778","volume":"18","author":[{"given":"Yushuai","family":"Ji","sequence":"first","affiliation":[{"name":"School of Computer Science, Wuhan University"}]},{"given":"Shengkun","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University"}]},{"given":"Shixun","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computing and Information Technology, The University of Wollongong"}]},{"given":"Zepeng","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University"}]},{"given":"Sheng","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University"}]},{"given":"Zhiyong","family":"Peng","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University and Big Data Institute, Wuhan University"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2025. Amazon Product Reviews. https:\/\/cseweb.ucsd.edu\/~jmcauley\/datasets.html#amazon_reviews."},{"key":"e_1_2_1_2_1","unstructured":"2025. Gaming Profiles 2025 (Steam PlayStation Xbox). https:\/\/www.kaggle.com\/datasets\/artyomkruglov\/gaming-profiles-2025-steam-playstation-xbox."},{"key":"e_1_2_1_3_1","unstructured":"2025. Global Fashion Retail Sales. https:\/\/www.kaggle.com\/datasets\/ricgomes\/global-fashion-retail-stores-dataset\/data?select=customers.csv."},{"key":"e_1_2_1_4_1","unstructured":"2025. GroupLens Research collects ratings data from the MovieLens website. https:\/\/grouplens.org\/datasets\/movielens\/."},{"key":"e_1_2_1_5_1","unstructured":"2025. HMDA Data Browser allows you to filter aggregate download and visualize HMDA datasets. https:\/\/ffiec.cfpb.gov\/data-browser\/."},{"key":"e_1_2_1_6_1","unstructured":"2025. NYC Open Data. https:\/\/opendata.cityofnewyork.us\/."},{"key":"e_1_2_1_7_1","unstructured":"2025. Repository of Teb-means. https:\/\/github.com\/whu-totemdb\/Teb-means."},{"key":"e_1_2_1_8_1","unstructured":"2025. UCI Credit Card. https:\/\/archive.ics.uci.edu\/dataset\/183\/communities+and+crime."},{"key":"e_1_2_1_9_1","unstructured":"2025. US Census Data. https:\/\/archive.ics.uci.edu\/dataset\/116\/us+census+data+1990."},{"key":"e_1_2_1_10_1","volume-title":"Informatiktage","author":"Althoff Tim","unstructured":"Tim Althoff, Adrian Ulges, and Andreas Dengel. 2011. Balanced Clustering for Content-based Image Browsing. In Informatiktage, Vol. S-10. 27\u201330."},{"key":"e_1_2_1_11_1","volume-title":"Redmond 20","author":"Bradley Paul S","year":"2000","unstructured":"Paul S Bradley, Kristin P Bennett, and Ayhan Demiriz. 2000. Constrained k-means clustering. Microsoft Research, Redmond 20 (2000)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3508057"},{"key":"e_1_2_1_13_1","volume-title":"SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NeurIPS. 5199\u20135212.","author":"Chen Qi","year":"2021","unstructured":"Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NeurIPS. 5199\u20135212."},{"key":"e_1_2_1_14_1","unstructured":"Yixin Chen Ya Zhang and Xiang Ji. 2005. Size Regularized Cut for Data Clustering. In NIPS. 211\u2013218."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_16_1","first-page":"1339","article-title":"K-Means Clustering with Distributed Dimensions","volume":"48","author":"Ding Hu","year":"2016","unstructured":"Hu Ding, Yu Liu, Lingxiao Huang, and Jian Li. 2016. K-Means Clustering with Distributed Dimensions. In ICML, Vol. 48. 1339\u20131348.","journal-title":"ICML"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735481"},{"key":"e_1_2_1_18_1","unstructured":"Jonathan Drake. 2013. Faster k-means Clustering. In MS Thesis."},{"key":"e_1_2_1_19_1","unstructured":"Charles Elkan. 2003. Using the triangle inequality to accelerate k-means. In ICML. 147\u2013153."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1209854"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407813"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Fangcheng Fu Huanran Xue Yong Cheng Yangyu Tao and Bin Cui. 2022. BlindFL: Vertical Federated Machine Learning without Peeking into Your Data. In SIGMOD. 1316\u20131330.","DOI":"10.1145\/3514221.3526127"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Siddharth Gollapudi Neel Karia Varun Sivashankar Ravishankar Krishnaswamy Nikit Begwani Swapnil Raz Yiyong Lin Yin Zhang Neelam Mahapatro Premkumar Srinivasan Amit Singh and Harsha Vardhan Simhadri. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. 3406\u20133416.","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_1_24_1","unstructured":"Lingxiao Huang Zhize Li Jialin Sun and Haoyu Zhao. 2022. Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering. In NeurIPS."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yushuai Ji Zepeng Liu Sheng Wang Yuan Sun and Zhiyong Peng. 2025. On Simplifying Large-Scale Spatial Vectors: Fast Memory-Efficient and Cost-Predictable k-means. In ICDE. 863\u2013876.","DOI":"10.1109\/ICDE65448.2025.00070"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3685800.3685900"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000083"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"He Li Lu Yu and Wu He. 2019. The impact of GDPR on global technology development. 6 pages.","DOI":"10.1080\/1097198X.2019.1569186"},{"key":"e_1_2_1_29_1","first-page":"3129","article-title":"An Accurate and Efficient Large-Scale Regression Method Through Best Friend Clustering","volume":"33","author":"Li Kun","year":"2022","unstructured":"Kun Li, Liang Yuan, Yunquan Zhang, and Gongwei Chen. 2022. An Accurate and Efficient Large-Scale Regression Method Through Best Friend Clustering. IEEE Trans. Parallel Distributed Syst. 33, 11 (2022), 3129\u20133140.","journal-title":"IEEE Trans. Parallel Distributed Syst."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583146"},{"key":"e_1_2_1_31_1","unstructured":"Hanyang Liu Junwei Han Feiping Nie and Xuelong Li. 2017. Balanced Clustering with Least Square Regression. In AAAI. 2231\u20132237."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8621917"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2022.3198176"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_35_1","volume-title":"Malinen and Pasi Franti","author":"Mikko","year":"2014","unstructured":"Mikko I. Malinen and Pasi Franti. 2014. Balanced K-Means for Clustering. In S+SSPR, Vol. 8621. Springer, 32\u201341."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587147"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3155450"},{"key":"e_1_2_1_38_1","first-page":"2371","article-title":"Coordinate Descent Method for k-means","volume":"44","author":"Nie Feiping","year":"2022","unstructured":"Feiping Nie, Jingjing Xue, Danyang Wu, Rong Wang, Hui Li, and Xuelong Li. 2022. Coordinate Descent Method for k-means. IEEE Trans. Pattern Anal. Mach. Intell. 44, 5 (2022), 2371\u20132385.","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"e_1_2_1_39_1","first-page":"1143","article-title":"Standardized Mutual Information for Clustering Comparisons: One Step Further in Adjustment for Chance","volume":"32","author":"Romano Simone","year":"2014","unstructured":"Simone Romano, James Bailey, Xuan Vinh Nguyen, and Karin Verspoor. 2014. Standardized Mutual Information for Clustering Comparisons: One Step Further in Adjustment for Chance. In ICML, Vol. 32. 1143\u20131151.","journal-title":"ICML"},{"key":"e_1_2_1_40_1","first-page":"175","article-title":"On the Use of the Adjusted Rand Index as a Metric for Evaluating Supervised Classification","volume":"5769","author":"Santos Jorge M.","year":"2009","unstructured":"Jorge M. Santos and Mark J. Embrechts. 2009. On the Use of the Adjusted Rand Index as a Metric for Evaluating Supervised Classification. In ICANN, Vol. 5769. 175\u2013184.","journal-title":"ICANN"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-024-00894-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654990"},{"key":"e_1_2_1_43_1","volume-title":"A Survey on Trajectory Data Management, Analytics, and Learning. ACM Comput. Surv. 54, 2","author":"Wang Sheng","year":"2022","unstructured":"Sheng Wang, Zhifeng Bao, J. Shane Culpepper, and Gao Cong. 2022. A Survey on Trajectory Data Management, Analytics, and Learning. ACM Comput. Surv. 54, 2 (2022), 39:1\u201339:36."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425887"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Yuming Xu Hengyu Liang Jin Li Shuotao Xu Qi Chen Qianxi Zhang Cheng Li Ziyue Yang Fan Yang Yuqing Yang Peng Cheng and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In SOSP. 545\u2013561.","DOI":"10.1145\/3600006.3613166"},{"key":"e_1_2_1_46_1","article-title":"Federated Machine Learning","volume":"10","author":"Yang Qiang","year":"2019","unstructured":"Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. 2019. Federated Machine Learning: Concept and Applications. ACM Trans. Intell. Syst. Technol. 10, 2 (2019), 12:1\u201312:19.","journal-title":"Concept and Applications. ACM Trans. Intell. Syst. Technol."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587141"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2022.3160244"},{"key":"e_1_2_1_49_1","first-page":"103","article-title":"An Efficient Energy-Hole Alleviating Algorithm for Wireless Sensor Network Based on Energy-Balanced Clustering Protocol","volume":"812","author":"Zhou Weiwei","year":"2017","unstructured":"Weiwei Zhou and Bin Yu. 2017. An Efficient Energy-Hole Alleviating Algorithm for Wireless Sensor Network Based on Energy-Balanced Clustering Protocol. In CWSN, Vol. 812. 103\u2013116.","journal-title":"CWSN"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2014.08.006"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626728"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3685800.3685895"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:39:19Z","timestamp":1757043559000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":52,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749673"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749673","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}