{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:10:40Z","timestamp":1772467840967,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation CAREER","award":["1350766, 1618706 and 1717774"],"award-info":[{"award-number":["1350766, 1618706 and 1717774"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>Detecting strongly connected components (SCCs) in a directed graph is crucial for understanding the structure of graphs. Most real-world graphs have one large SCC that contains the majority of the vertices as well as many small SCCs whose sizes are reversely proportional to the frequency of their occurrences. For both types of SCCs, current approaches that rely on depth first search (DFS) or breadth first search (BFS) face the challenges of both strict synchronization requirements and high computation cost. In this article, we advocate a new paradigm of identifying SCCs with simple spanning trees since SCC detection requires only the knowledge of connectivity among the vertices. We have developed a prototype called<jats:sc>i<\/jats:sc><jats:sc>S<\/jats:sc><jats:sc>pan<\/jats:sc>, which consists of parallel, relaxed synchronization construction of spanning trees for detecting large and small SCCs combined with fast trims for small SCCs. We further scale<jats:sc>i<\/jats:sc><jats:sc>S<\/jats:sc><jats:sc>pan<\/jats:sc>to the distributed memory system by applying different distribution strategies to the data and task parallel jobs. Not limited, we also extend<jats:sc>i<\/jats:sc><jats:sc>S<\/jats:sc><jats:sc>pan<\/jats:sc>to the GPU architecture. The evaluations show that<jats:sc>i<\/jats:sc><jats:sc>S<\/jats:sc><jats:sc>pan<\/jats:sc>is able to significantly outperform current state-of-the-art DFS- and BFS-based methods by an average 18\u00d7 and 4\u00d7, respectively.<\/jats:p>","DOI":"10.1145\/3543542","type":"journal-article","created":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T09:04:34Z","timestamp":1657271074000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["<scp>i<\/scp><scp>S<\/scp><scp>pan<\/scp>: Parallel Identification of Strongly Connected Components with Spanning Trees"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2419-6592","authenticated-orcid":false,"given":"Yuede","family":"Ji","sequence":"first","affiliation":[{"name":"University of North Texas, Denton, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6323-7388","authenticated-orcid":false,"given":"Hang","family":"Liu","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, Hoboken, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1665-1794","authenticated-orcid":false,"given":"Yang","family":"Hu","sequence":"additional","affiliation":[{"name":"George Washington University, Washington, DC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8588-7680","authenticated-orcid":false,"given":"H. Howie","family":"Huang","sequence":"additional","affiliation":[{"name":"George Washington University, Washington, DC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807651"},{"key":"e_1_3_2_3_2","unstructured":"Alfred V. Aho Jeffrey D. Ullman and John E. Hopcroft. 1983. Data structures and algorithms. Addison-Wesley USA."},{"key":"e_1_3_2_4_2","first-page":"22","volume-title":"2016 IEEE International Parallel and Distributed Processing Symposium","author":"Arai Junya","year":"2016","unstructured":"Junya Arai, Hiroaki Shiokawa, Takeshi Yamamuro, Makoto Onizuka, and Sotetsu Iwamura. 2016. Rabbit order: Just-in-time parallel reordering for fast graph analysis. In 2016 IEEE International Parallel and Distributed Processing Symposium, Chicago, Illinois USA. IEEE, 22\u201331."},{"key":"e_1_3_2_5_2","unstructured":"David A. Bader and Kamesh Madduri. 2006. Gtgraph: A synthetic graph generator suite. Technical Report Georgia Institute of Technology Atlanta GA USA."},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1109\/IPDPS.2011.59","volume-title":"International Parallel and Distributed Processing Symposium (IPDPS\u201911)","author":"Barnat Ji\u0159\u00ed","year":"2011","unstructured":"Ji\u0159\u00ed Barnat, Petr Bauch, Lubo\u0161 Brim, and Milan Ceska. 2011. Computing strongly connected components in parallel on CUDA. In International Parallel and Distributed Processing Symposium (IPDPS\u201911), Anchorage, Alaska USA. IEEE, 544\u2013555."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"1618","DOI":"10.1109\/IPDPSW.2013.159","volume-title":"2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW\u201913)","author":"Beamer Scott","year":"2013","unstructured":"Scott Beamer, Aydin Buluc, Krste Asanovic, and David Patterson. 2013. Distributed memory breadth-first search revisited: Enabling bottom-up search. In 2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW\u201913), Boston, Massachusetts USA. IEEE, 1618\u20131627."},{"key":"e_1_3_2_9_2","first-page":"235","volume-title":"ACM SIGPLAN Notices","author":"Ben-Nun Tal","year":"2017","unstructured":"Tal Ben-Nun, Michael Sutton, Sreepathi Pai, and Keshav Pingali. 2017. Groute: An asynchronous multi-GPU programming model for irregular computations. In ACM SIGPLAN Notices, Vol. 52, New York, NY, USA. ACM, 235\u2013248."},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"Maciej Besta Florian Marending Edgar Solomonik and Torsten Hoefler. SlimSell: A vectorizable graph representation for breadth-first search. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS) . IEEE Orlando Florida USA 32\u201341.","DOI":"10.1109\/IPDPS.2017.93"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851161"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_3_2_13_2","first-page":"233","volume-title":"Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures (SPAA\u201909)","author":"Bulu\u00e7 Aydin","year":"2009","unstructured":"Aydin Bulu\u00e7, Jeremy T. Fineman, Matteo Frigo, John R. Gilbert, and Charles E. Leiserson. 2009. Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks. In Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures (SPAA\u201909), Calgary, Canada. ACM, 233\u2013244."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063471"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Karen D. Devine Erik G. Boman Robert T. Heaphy Rob H. Bisseling and Umit V. Catalyurek. 2006. Parallel hypergraph partitioning for scientic computing. In Proceedings 20th IEEE International Parallel & Distributed Processing Symposium . IEEE Rhodes Greece 10\u2013pp.","DOI":"10.1109\/IPDPS.2006.1639359"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2884045.2884048"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2141702.2141714"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920986"},{"key":"e_1_3_2_19_2","first-page":"505","volume-title":"International Parallel and Distributed Processing Symposium (IPDPS\u201900)","author":"Fleischer Lisa K.","year":"2000","unstructured":"Lisa K. Fleischer, Bruce Hendrickson, and Ali P\u0131nar. 2000. On identifying strongly connected components in parallel. In International Parallel and Distributed Processing Symposium (IPDPS\u201900), Cancun, Mexico. Springer, 505\u2013511."},{"issue":"39","key":"e_1_3_2_20_2","first-page":"851","article-title":"Parallel prefix sum (scan) with CUDA","volume":"3","author":"Harris Mark","year":"2007","unstructured":"Mark Harris, Shubhabrata Sengupta, and John D. Owens. 2007. Parallel prefix sum (scan) with CUDA. GPU gems 3, 39 (2007), 851\u2013876.","journal-title":"GPU gems"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56922-7_5"},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","unstructured":"Sungpack Hong Nicole C. Rodia and Kunle Olukotun. 2013. On fast parallel detection of strongly connected components (SCC) in small-world graphs. In Proceedings of the International Conference on High Performance Computing Networking Storage and Analysis . ACM Denver Colorado USA 1\u201311.","DOI":"10.1145\/2503210.2503246"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"Jayadharini Jaiganesh and Martin Burtscher. 2018. A high-performance connected components implementation for GPUs. In Proceedings of the 27th International Symposium on High-Performance Parallel and Distributed Computing . ACM Tempe Arizona USA 92\u2013104.","DOI":"10.1145\/3208040.3208041"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"Yuede Ji and H. Howie Huang. 2020. Aquila: Adaptive parallel computation of graph connectivity queries. In Proceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing . ACM Stockholm Sweden 149\u2013160.","DOI":"10.1145\/3369583.3392690"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Yuede Ji Hang Liu and H. Howie Huang. 2020. Swarmgraph: Analyzing large-scale in-memory graphs on gpus. In 2020 IEEE 22nd International Conference on High Performance Computing and Communications; IEEE 18th International Conference on Smart City; IEEE 6th International Conference on Data Science and Systems (HPCC\/SmartCity\/DSS) . IEEE Fiji 52\u201359.","DOI":"10.1109\/HPCC-SmartCity-DSS50907.2020.00008"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.80"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/978-1-4419-6515-8_13","volume-title":"Link mining: Models, algorithms, and applications","author":"Kumar Ravi","year":"2010","unstructured":"Ravi Kumar, Jasmine Novak, and Andrew Tomkins. 2010. Structure and evolution of online social networks. In Link mining: Models, algorithms, and applications, New York, NY. Springer, 337\u2013357."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2833179.2833188"},{"key":"e_1_3_2_30_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved July 11, 2022 from http:\/\/snap.stanford.edu\/data.","journal-title":"http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807594"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.03.007"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","unstructured":"Duane Merrill Michael Garland and Andrew Grimshaw. 2012. Scalable GPU graph traversal. In ACM SIGPLAN Notices Vol. 47. ACM Philadelphia Pennsylvania USA 117\u2013128.","DOI":"10.1145\/2370036.2145832"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397742"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_38_2","article-title":"On Distributed Verification and Verified Distribution","author":"Orzan Simona Mihaela","year":"2004","unstructured":"Simona Mihaela Orzan. 2004. On Distributed Verification and Verified Distribution. Ph.D. Dissertation. Vrije Universiteit, Amsterdam, Netherlands.","journal-title":"Ph.D. Dissertation."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.70"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915238"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2014.7116914"},{"key":"e_1_3_2_44_2","first-page":"550","volume-title":"International Parallel and Distributed Processing Symposium (IPDPS\u201914)","author":"Slota George M.","year":"2014","unstructured":"George M. Slota, Sivasankaran Rajamanickam, and Kamesh Madduri. 2014. BFS and coloring-based parallel algorithms for strongly connected components and related problems. In International Parallel and Distributed Processing Symposium (IPDPS\u201914), Phoenix, AZ USA. IEEE, 550\u2013559."},{"key":"e_1_3_2_45_2","first-page":"293","volume-title":"2016 IEEE International Parallel and Distributed Processing Symposium","author":"Slota George M.","year":"2016","unstructured":"George M. Slota, Sivasankaran Rajamanickam, and Kamesh Madduri. 2016. A case study of complex graph analysis in distributed memory: Implementation and optimization. In 2016 IEEE International Parallel and Distributed Processing Symposium, Chicago, IL USA. IEEE, 293\u2013302."},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","unstructured":"Sriram Srinivasan Sanjukta Bhowmick and Sajal Das. 2016. Application of Graph Sparsication in Developing Parallel Algorithms for Updating Connected Components. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) . IEEE Chicago Illinois USA 885\u2013891.","DOI":"10.1109\/IPDPSW.2016.180"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_48_2","first-page":"3","volume-title":"CIDR\u201913","author":"Wang Guozhang","year":"2013","unstructured":"Guozhang Wang, Wenlei Xie, Alan J. Demers, and Johannes Gehrke. 2013. Asynchronous large-scale graph processing made easy. In CIDR\u201913, Vol. 13, Asilomar, California USA. 3\u20136."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733089"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463703"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543542","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543542","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:47Z","timestamp":1750186847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3543542"],"URL":"https:\/\/doi.org\/10.1145\/3543542","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,18]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}