{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:20:32Z","timestamp":1766269232119,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":92,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DOE Early Career Award","award":["DE-SC0018947"],"award-info":[{"award-number":["DE-SC0018947"]}]},{"name":"Google Faculty Research Award"},{"name":"NSF CAREER Award","award":["CCF-1845763"],"award-info":[{"award-number":["CCF-1845763"]}]},{"name":"Applications Driving Architectures (ADA) Research Center"},{"name":"DARPA SDH Award","award":["HR0011-18-3-0007"],"award-info":[{"award-number":["HR0011-18-3-0007"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,9,30]]},"DOI":"10.1145\/3410463.3414657","type":"proceedings-article","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T10:43:04Z","timestamp":1601462584000},"page":"55-69","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Exploring the Design Space of Static and Incremental Graph Connectivity Algorithms on GPUs"],"prefix":"10.1145","author":[{"given":"Changwan","family":"Hong","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"volume-title":"Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 381--392","year":"2019","author":"Acar Umut A.","key":"e_1_3_2_1_1_1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676869"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.03.011"},{"volume-title":"On the Architectural Requirements for Efficient Execution of Graph Algorithms. In International Conference on Parallel Processing (ICPP). 547--556","year":"2005","author":"Bader David A.","key":"e_1_3_2_1_5_1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0079"},{"volume-title":"Hybrid Algorithms for List Ranking and Graph Connected Components. In International Conference on High Performance Computing (HiPC). 1--10","year":"2011","author":"Banerjee Dip Sankar","key":"e_1_3_2_1_7_1"},{"volume-title":"Scale-Free Networks. Scientific American","year":"2003","author":"Barabasi Albert-Laszlo","key":"e_1_3_2_1_8_1"},{"key":"e_1_3_2_1_9_1","first-page":"1","article-title":"Direction-optimizing breadth-first search. In ACM\/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC)","volume":"12","author":"Beamer Scott","year":"2012","journal-title":"Article"},{"volume-title":"Patterson","year":"2015","author":"Beamer Scott","key":"e_1_3_2_1_10_1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00095"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323208"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018756"},{"volume-title":"Internally Deterministic Parallel Algorithms Can Be Fast. In ACM SIGPLAN Symposium on Proceedings of Principles and Practice of Parallel Programming (PPoPP). 181--192","year":"2012","author":"Blelloch Guy E.","key":"e_1_3_2_1_14_1"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Libor Bus and Pavel Tvrdik. 2001. A Parallel Algorithm for Connected Components on Distributed Memory Machines. In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 280--287.  Libor Bus and Pavel Tvrdik. 2001. A Parallel Algorithm for Connected Components on Distributed Memory Machines. In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 280--287.","DOI":"10.1007\/3-540-45417-9_39"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2018.8547541"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"E.N. Caceres F. Dehne H. Mongelli S.W. Song and J.L. Szwarcfiter. 2004. A Coarse-Grained Parallel Algorithm for Spanning Tree and Connected Components. In Euro-Par.  E.N. Caceres F. Dehne H. Mongelli S.W. Song and J.L. Szwarcfiter. 2004. A Coarse-Grained Parallel Algorithm for Spanning Tree and Connected Components. In Euro-Par.","DOI":"10.1007\/978-3-540-27866-5_110"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555253"},{"volume-title":"R-MAT: A Recursive Model for Graph Mining. In SIAM International Conference on Data Mining (SDM). 442--446","year":"2004","author":"Chakrabarti Deepayan","key":"e_1_3_2_1_19_1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/358628.358650"},{"volume-title":"Finding Connected Components in Map-Reduce in Logarithmic Rounds. In IEEE International Conference on Data Engineering (ICDE). 50--61","year":"2013","author":"Chitnis Laukik","key":"e_1_3_2_1_21_1"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1016"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90019-X"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Guojing Cong and Paul Muzio. 2014. Fast Parallel Connected Components Algorithms on GPUs. In Euro-Par. 153--164.  Guojing Cong and Paul Muzio. 2014. Fast Parallel Connected Components Algorithms on GPUs. In Euro-Par. 153--164.","DOI":"10.1007\/978-3-319-14325-5_14"},{"volume-title":"Introduction to Algorithms (3. ed.)","author":"Cormen Thomas H.","key":"e_1_3_2_1_25_1"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"volume-title":"Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 393--404","year":"2018","author":"Dhulipala Laxman","key":"e_1_3_2_1_27_1"},{"volume-title":"Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 1300--1319","year":"2020","author":"Dhulipala Laxman","key":"e_1_3_2_1_28_1"},{"key":"e_1_3_2_1_29_1","unstructured":"Laxman Dhulipala Changwan Hong and Julian Shun. 2020. ConnectIt: A framework for static and incremental parallel graph connectivity algorithms. https:\/\/arxiv.org\/abs\/2008.03909  Laxman Dhulipala Changwan Hong and Julian Shun. 2020. ConnectIt: A framework for static and incremental parallel graph connectivity algorithms. https:\/\/arxiv.org\/abs\/2008.03909"},{"volume-title":"IEEE Conference on High Performance Extreme Computing (HPEC). 1--5.","author":"Ediger D.","key":"e_1_3_2_1_30_1"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.57"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00040"},{"volume-title":"International Conference on Knowledge Discovery and Data Mining (KDD). 226--231","year":"1996","author":"Ester Martin","key":"e_1_3_2_1_33_1"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220066"},{"volume-title":"IEEE High Performance Extreme Computing Conference (HPEC). 1--6.","author":"Green O.","key":"e_1_3_2_1_35_1"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/181014.181021"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/181014.181017"},{"volume-title":"International Conference on Supercomputing (ICS). 477--483","author":"Hambrusch S.","key":"e_1_3_2_1_38_1"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214077"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2010.07.002"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/13691180500146185"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/359138.359141"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2003.1211332"},{"volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS). 896--909","author":"Holm J.","key":"e_1_3_2_1_44_1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Changwan Hong Laxman Dhulipala and Julian Shun. 2020. Exploring the Design Space of Static and Incremental Graph Connectivity Algorithms on GPUs. http:\/\/arxiv.org\/abs\/2008.11839  Changwan Hong Laxman Dhulipala and Julian Shun. 2020. Exploring the Design Space of Static and Incremental Graph Connectivity Algorithms on GPUs. http:\/\/arxiv.org\/abs\/2008.11839","DOI":"10.1145\/3410463.3414657"},{"volume-title":"Parallel Algorithms: 3rd DIMACS Implementation Challenge. 23--41.","author":"Hsu Tsan-Sheng","key":"e_1_3_2_1_46_1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"J. Iverson C. Kamath and G. Karypis. 2015. Evaluation of Connected-component Labeling Algorithms for Distributed-memory Systems. Parallel Comput. 44 C (May 2015) 53--68.  J. Iverson C. Kamath and G. Karypis. 2015. Evaluation of Connected-component Labeling Algorithms for Distributed-memory Systems. Parallel Comput. 44 C (May 2015) 53--68.","DOI":"10.1016\/j.parco.2015.02.005"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1009"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3208040.3208041"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2672739"},{"volume-title":"CUDA by example: an introduction to general-purpose GPU programming","year":"2010","author":"Jason Sanders","key":"e_1_3_2_1_51_1"},{"volume-title":"ACM Symposium on Principles of Distributed Computing (PODC). 75--82","author":"Siddhartha","key":"e_1_3_2_1_52_1"},{"volume-title":"Randomized Concurrent Set Union and Generalized Wake-Up. In ACM Symposium on Principles of Distributed Computing (PODC). 187--196","year":"2019","author":"Jayanti Siddhartha V.","key":"e_1_3_2_1_53_1"},{"volume-title":"Dissecting the NVIDIA Volta GPU architecture via microbenchmarking. arXiv preprint arXiv:1804.06826","year":"2018","author":"Jia Zhe","key":"e_1_3_2_1_54_1"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1291"},{"key":"e_1_3_2_1_56_1","first-page":"3","article-title":"Fast Connected Components Algorithms for the EREW PRAM","volume":"28","author":"Karger David R.","year":"1999","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_57_1","first-page":"1","article-title":"Connected Components in MapReduce and Beyond. In Proceedings of the ACM Symposium on Cloud Computing (SOCC)","volume":"18","author":"Kiveris Raimondas","year":"2014","journal-title":"Article"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Vaclav Koubek and Jana Krsnakova. 1985. Parallel algorithms for connected components in a graph. In Fundamentals of Computation Theory. 208--217.  Vaclav Koubek and Jana Krsnakova. 1985. Parallel algorithms for connected components in a graph. In Fundamentals of Computation Theory. 208--217.","DOI":"10.1007\/BFb0028804"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840376"},{"key":"e_1_3_2_1_60_1","unstructured":"Jure Leskovec and Andrej Krevl. 2019. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2019. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2005.862174"},{"key":"e_1_3_2_1_62_1","first-page":"1","article-title":"Simple Concurrent Labeling Algorithms for Connected Components","volume":"3","author":"Liu Sixue","year":"2019","journal-title":"Symposium on Simplicity in Algorithms (SOSA)."},{"volume-title":"IEEE International Parallel and Distributed Processing Symposium (IPDPS). 1--11","author":"Madduri Kamesh","key":"e_1_3_2_1_63_1"},{"volume-title":"IEEE International Conference on High Performance Computing (HiPC). 246--255","author":"McColl R.","key":"e_1_3_2_1_64_1"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295716"},{"volume-title":"Scalable GPU Graph Traversal. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 117--128","year":"2012","author":"Merrill Duane","key":"e_1_3_2_1_66_1"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90131-4"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_1_70_1","unstructured":"Molly A O'Neil Dan Tamir and Martin Burtscher. 2011. A parallel GPU version of the traveling salesman problem. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). The Steering Committee of The World Congress in Computer Science Computer Engineering and Applied Computing (WorldComp) 348--353.  Molly A O'Neil Dan Tamir and Martin Burtscher. 2011. A parallel GPU version of the traveling salesman problem. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). The Steering Committee of The World Congress in Computer Science Computer Engineering and Applied Computing (WorldComp) 348--353."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984015"},{"key":"e_1_3_2_1_72_1","first-page":"1","article-title":"A new scalable parallel DBSCAN algorithm using the disjoint-set data structure. In ACM\/IEEE International Conference on High Performance Computing","volume":"62","author":"Patwary M. M. A.","year":"2012","journal-title":"Networking, Storage and Analysis (SC)."},{"volume-title":"IEEE International Parallel and Distributed Processing Symposium (IPDPS). 827--835","key":"e_1_3_2_1_73_1"},{"volume-title":"Parallel Graph Contraction. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 148--157","year":"1989","author":"Phillips C. A.","key":"e_1_3_2_1_74_1"},{"volume-title":"Optimal Parallel Algorithms for Integer Sorting and Graph Connectivity. TR-08--85","year":"1985","author":"Reif J. H.","key":"e_1_3_2_1_75_1"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"crossref","unstructured":"Dipanjan Sengupta and Shuaiwen Leon Song. 2017. EvoGraph: On-the-Fly Efficient Mining of Evolving Graphs on GPU. In High Performance Computing. 97--119.  Dipanjan Sengupta and Shuaiwen Leon Song. 2017. EvoGraph: On-the-Fly Efficient Mining of Evolving Graphs on GPU. In High Performance Computing. 97--119.","DOI":"10.1007\/978-3-319-58667-0_6"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"volume-title":"Ligra: A Lightweight Graph Processing Framework for Shared Memory. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 135--146","author":"Shun Julian","key":"e_1_3_2_1_78_1"},{"volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 143--153","author":"Shun Julian","key":"e_1_3_2_1_79_1"},{"volume-title":"Work-efficient parallel union-find. Concurrency and Computation: Practice and Experience 30, 4","year":"2017","author":"Simsiri Natcha","key":"e_1_3_2_1_80_1"},{"volume-title":"BFS and Coloring-based Parallel Algorithms for Strongly Connected Components and Related Problems. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). 550--559","year":"2014","author":"Slota George M.","key":"e_1_3_2_1_81_1"},{"volume-title":"IEEE International Parallel and Distributed Processing Symposium (IPDPS). 1--8.","author":"Soman J.","key":"e_1_3_2_1_82_1"},{"volume-title":"Shortcutting Label Propagation for Distributed Connected Components. In ACM International Conference on Web Search and Data Mining (WSDM). 540--546","year":"2018","author":"Stergiou Stergios","key":"e_1_3_2_1_83_1"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555266"},{"volume-title":"IEEE International Parallel and Distributed Processing Symposium (IPDPS). 12--21","author":"Sutton M.","key":"e_1_3_2_1_85_1"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90019-2"},{"volume-title":"Owens","year":"2016","author":"Wang Yangzihao","key":"e_1_3_2_1_88_1"},{"key":"e_1_3_2_1_89_1","article-title":"Gunrock","volume":"4","author":"Wang Yangzihao","year":"2017","journal-title":"GPU Graph Analytics. ACM Trans. Parallel Comput."},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157795"},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"},{"volume-title":"FastSV: A DistributedMemory Connected Component Algorithm with Fast Convergence. CoRR abs\/1910.05971","year":"2019","author":"Zhang Yongzhe","key":"e_1_3_2_1_92_1"}],"event":{"name":"PACT '20: International Conference on Parallel Architectures and Compilation Techniques","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture"],"location":"Virtual Event GA USA","acronym":"PACT '20"},"container-title":["Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3410463.3414657","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3410463.3414657","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:58Z","timestamp":1750195918000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3410463.3414657"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":92,"alternative-id":["10.1145\/3410463.3414657","10.1145\/3410463"],"URL":"https:\/\/doi.org\/10.1145\/3410463.3414657","relation":{},"subject":[],"published":{"date-parts":[[2020,9,30]]},"assertion":[{"value":"2020-09-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}