{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T13:47:26Z","timestamp":1782481646314,"version":"3.54.5"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T00:00:00Z","timestamp":1782432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/legalcode"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2024YFB4504200"],"award-info":[{"award-number":["2024YFB4504200"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62421002 and 62025208"],"award-info":[{"award-number":["62421002 and 62025208"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Connected Components (CC) computation is a fundamental graph analytics kernel. While BFS-sampling has emerged as the state-of-the-art approach for power-law graphs, its performance in existing implementations is severely limited by inheriting unnecessary BFS semantics. The core issue is a fundamental mismatch: BFS requires strict level-synchronization to compute shortest paths, while CC only needs eventual label consistency without ordering constraints.<\/jats:p>\n                  <jats:p>This semantic mismatch manifests as three critical bottlenecks: (i) severe load imbalance from vertex-centric task allocation, which fails to distribute the massive workload of high-degree hub vertices; (ii) redundant writes from dynamic push\/pull mode switching, which necessitates costly frontier reconstruction; and (iii) redundant synchronization and computation from enforcing BFS\u2019s strict ordering guarantees, which are superfluous for CC computation.<\/jats:p>\n                  <jats:p>\n                    We introduce\n                    <jats:sc>FastCC<\/jats:sc>\n                    , a lightweight multiprocess system-algorithm co-designed solution that breaks this semantic mismatch. The cornerstone of our approach is the strategic decision to fix the highest-degree vertex as the BFS root, creating a predictable computation topology. This enables three synergistic innovations: (1) hybrid task partitioning that employs edge-centric allocation in the critical first iteration to eliminate load imbalance at its source; (2) predictable mode switching that leverages the deterministic computation graph to bypass expensive frontier reconstruction; and (3) lightweight, custom synchronization primitives that relax BFS\u2019s strict ordering to match CC\u2019s eventual consistency requirements, while allowing earlier label propagation within the same iteration to reduce the overall computational workload.\n                  <\/jats:p>\n                  <jats:p>\n                    Extensive evaluation on large-scale real-world and synthetic power-law graphs demonstrates that\n                    <jats:sc>FastCC<\/jats:sc>\n                    achieves significant performance improvements, with speedups of 10.6-55.5\u00d7 faster (average: 37.8\u00d7) over state-of-the-art CC implementations including ConnectIt and vGraph.\n                    <jats:sc>FastCC<\/jats:sc>\n                    also reduces peak memory footprint by up to 2.87\u00d7 and exhibits superior, more predictable scalability. The practical efficacy of our approach is validated by its deployment as the core engine in a top-ranked GreenGraph500 solution.\n                  <\/jats:p>","DOI":"10.1145\/3803020","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T21:01:02Z","timestamp":1773867662000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["FastCC: A System-Algorithm Co-Design for Connected Components Computation on Large Power-Law Graphs"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5639-7882","authenticated-orcid":false,"given":"Menghan","family":"Jia","sequence":"first","affiliation":[{"name":"National Key Laboratory of Parallel and Distributed Computing, College of Computer Science and Technology, National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7564-5239","authenticated-orcid":false,"given":"Yongquan","family":"Fu","sequence":"additional","affiliation":[{"name":"National Key Laboratory of Parallel and Distributed Computing, College of Computer Science and Technology, National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6450-8485","authenticated-orcid":false,"given":"Yiming","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2931-4893","authenticated-orcid":false,"given":"Xinhai","family":"Chen","sequence":"additional","affiliation":[{"name":"National Key Laboratory of Parallel and Distributed Computing, College of Computer Science and Technology, National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9743-2034","authenticated-orcid":false,"given":"Dongsheng","family":"Li","sequence":"additional","affiliation":[{"name":"National Key Laboratory of Parallel and Distributed Computing, College of Computer Science and Technology, National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,26]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3607071"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_3_1_4_2","unstructured":"S. Beamer K. Asanovi\u0107 and D. Patterson. 2017. The GAP Benchmark Suite. arxiv:1508.03619. Retrieved from https:\/\/arxiv.org\/abs\/1508.03619"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3078597.3078616"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145840"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436923"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3660258"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2022.3217403"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3100785"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-52470-7_12"},{"key":"e_1_3_1_14_2","volume-title":"Proceedings of the 1st USENIX Workshop on Offensive Technologies","author":"Gundy M. Van","year":"2007","unstructured":"M. Van Gundy, D. Balzarotti, and G. Vigna. 2007. Catch me, if you can: Evading network signatures with web-based polymorphic worms. In Proceedings of the 1st USENIX Workshop on Offensive Technologies. USENIX Association. Retrieved from https:\/\/www.usenix.org\/legacy\/events\/woot07\/tech\/full_papers\/vangundy\/vangundy.pdf"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.3390\/a12120270"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3208040.3208041"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933108"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00068"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00089"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_1_21_2","unstructured":"J. Leskovec D. Chakrabarti J. Kleinberg C. Faloutsos and Z. Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research 11 33 (2010) 985\u20131042."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00233"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2019.3"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154750"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3639413"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.79"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00012"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","unstructured":"D. Tench E. West V. Zhang M. A. Bender A. Chowdhury D. Delayo J. A. Dellas M. Farach-Colton T. Seip and K. Zhang. 2024. GraphZeppelin: How to find connected components (even when graphs are dense dynamic and massive). ACM Transactions on Database Systems 49 3 Article 9 (September 2024) 31. DOI:10.1145\/3643846","DOI":"10.1145\/3643846"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-169"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2023.3305077"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3803020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T12:57:09Z","timestamp":1782478629000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3803020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,26]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3803020"],"URL":"https:\/\/doi.org\/10.1145\/3803020","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,26]]},"assertion":[{"value":"2025-11-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}