{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:38:22Z","timestamp":1770917902783,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":77,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T00:00:00Z","timestamp":1708387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"name":"SNSF","award":["2ELP2_195126"],"award-info":[{"award-number":["2ELP2_195126"]}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/100000015","name":"DOE U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0018947"],"award-info":[{"award-number":["DE-SC0018947"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1845763"],"award-info":[{"award-number":["CCF-1845763"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/100017567","name":"Apple","doi-asserted-by":"publisher","id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/100017567","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,3,2]]},"DOI":"10.1145\/3627535.3638508","type":"proceedings-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T14:22:41Z","timestamp":1708438961000},"page":"286-300","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Parallel k-Core Decomposition with Batched Updates and Asynchronous Reads"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1230-2754","authenticated-orcid":false,"given":"Quanquan C.","family":"Liu","sequence":"first","affiliation":[{"name":"Yale University, New Haven, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6163-6625","authenticated-orcid":false,"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9271-518X","authenticated-orcid":false,"given":"Igor","family":"Zablotchi","sequence":"additional","affiliation":[{"name":"Mysten Labs, Z\u00fcrich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2024,2,20]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Parallel Batch-Dynamic Graph Connectivity. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures. 381--392","author":"Acar Umut A.","year":"2019","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. 2019. Parallel Batch-Dynamic Graph Connectivity. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures. 381--392."},{"key":"e_1_3_2_1_2_1","volume-title":"Annual European Symposium on Algorithms","volume":"173","author":"Acar Umut A.","year":"2020","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-Dynamic Trees via Change Propagation. In Annual European Symposium on Algorithms, Vol. 173. 2:1--2:23."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612688"},{"key":"e_1_3_2_1_5_1","volume-title":"Parallel Combining: Benefits of Explicit Synchronization. In International Conference on Principles of Distributed Systems (OPODIS)","volume":"125","author":"Aksenov Vitaly","year":"2018","unstructured":"Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto. 2018. Parallel Combining: Benefits of Explicit Synchronization. In International Conference on Principles of Distributed Systems (OPODIS), Vol. 125. 11:1--11:16."},{"key":"e_1_3_2_1_6_1","volume-title":"In Search of the Fastest Concurrent Union-Find Algorithm. In 23rd International Conference on Principles of Distributed Systems","volume":"153","author":"Alistarh Dan","year":"2019","unstructured":"Dan Alistarh, Alexander Fedorov, and Nikita Koval. 2019. In Search of the Fastest Concurrent Union-Find Algorithm. In 23rd International Conference on Principles of Distributed Systems, Vol. 153. 15:1--15:16."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-207"},{"key":"e_1_3_2_1_8_1","unstructured":"J. Ignacio Alvarez-Hamelin Luca Dall'Asta Alain Barrat and Alessandro Vespignani. 2005. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems. 41--50."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2306.08786"},{"key":"e_1_3_2_1_10_1","volume-title":"Efficient Parallel Self-Adjusting Computation. In 33rd ACM Symposium on Parallelism in Algorithms and Architectures. 59--70","author":"Anderson Daniel","unstructured":"Daniel Anderson, Guy E. Blelloch, Anubhav Baweja, and Umut A. Acar. 2021. Efficient Parallel Self-Adjusting Computation. In 33rd ACM Symposium on Parallelism in Algorithms and Architectures. 59--70."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933267.2933299"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-4-2"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165265"},{"key":"e_1_3_2_1_15_1","volume-title":"Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In ACM Symposium on Theory of Computing (STOC). 173--182","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. 2015. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In ACM Symposium on Theory of Computing (STOC). 173--182."},{"key":"e_1_3_2_1_16_1","volume-title":"Brief Announcement: ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In ACM Symp. on Parallel Alg. (SPAA). 507--509","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. Brief Announcement: ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In ACM Symp. on Parallel Alg. (SPAA). 507--509."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_3_2_1_18_1","volume-title":"USENIX Annual Technical Conference (ATC), Andrew Birrell and Emin G\u00fcn Sirer (Eds.). 49--60","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry C. Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkateshwaran Venkataramani. 2013. TAO: Facebook's Distributed Data Store for the Social Graph. In USENIX Annual Technical Conference (ATC), Andrew Birrell and Emin G\u00fcn Sirer (Eds.). 49--60. https:\/\/www.usenix.org\/conference\/atc13\/technical-sessions\/presentation\/bronson"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3538598.3538616"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00065"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-020-69464-3"},{"key":"e_1_3_2_1_23_1","volume-title":"The Inherent Cost of Remembering Consistently. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 259--269","author":"Cohen Nachshon","year":"2018","unstructured":"Nachshon Cohen, Rachid Guerraoui, and Igor Zablotchi. 2018. The Inherent Cost of Remembering Consistently. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 259--269."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523733"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_2_1_26_1","volume-title":"Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 393--404","author":"Dhulipala Laxman","year":"2018","unstructured":"Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2018. Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 393--404."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436923"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.10"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1513876.1513879"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835736"},{"key":"e_1_3_2_1_32_1","volume-title":"International Conference on Extending Database Technology (EDBT). 325--336","author":"Esfahani Fatemeh","year":"2019","unstructured":"Fatemeh Esfahani, Venkatesh Srinivasan, Alex Thomo, and Kui Wu. 2019. Efficient Computation of Probabilistic Core Decomposition at Web-Scale. In International Conference on Extending Database Technology (EDBT). 325--336."},{"key":"e_1_3_2_1_33_1","volume-title":"Parallel and Streaming Algorithms for K-Core Decomposition. In International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research","volume":"1405","author":"Esfandiari Hossein","unstructured":"Hossein Esfandiari, Silvio Lattanzi, and Vahab S. Mirrokni. 2018. Parallel and Streaming Algorithms for K-Core Decomposition. In International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research, Vol. 80). 1396--1405."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461810"},{"key":"e_1_3_2_1_36_1","volume-title":"Batch Dynamic Algorithms for Two Graph Problems. In International PARLE Conference on Parallel Architectures and Languages Europe","volume":"817","author":"Ferragina Paolo","year":"1994","unstructured":"Paolo Ferragina and Fabrizio Luccio. 1994. Batch Dynamic Algorithms for Two Graph Problems. In International PARLE Conference on Parallel Architectures and Languages Europe, Vol. 817. 713--724."},{"key":"e_1_3_2_1_37_1","volume-title":"Practical lock-freedom. Ph. D. Dissertation","author":"Fraser Keir","unstructured":"Keir Fraser. 2004. Practical lock-freedom. Ph. D. Dissertation. University of Cambridge, UK."},{"key":"e_1_3_2_1_38_1","volume-title":"IEEE International Parallel and Distributed Processing Symposium (IPDPS) Workshops. 998--1007","author":"Gabert Kasimir","year":"2021","unstructured":"Kasimir Gabert, Ali Pinar, and \u00dcmit V. \u00c7ataly\u00fcrek. 2021. Shared-Memory Scalable k-Core Maintenance on Dynamic Graphs and Hypergraphs. In IEEE International Parallel and Distributed Processing Symposium (IPDPS) Workshops. 998--1007."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_3_2_1_40_1","volume-title":"Improved Parallel Algorithms for Density-Based Network Clustering. In International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research","volume":"2210","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research, Vol. 97). 2201--2210."},{"key":"e_1_3_2_1_41_1","volume-title":"CoreCluster: A Degeneracy Based Graph Clustering Framework. In AAAI Conference on Artificial Intelligence. 44--50","author":"Giatsidis Christos","year":"2014","unstructured":"Christos Giatsidis, Fragkiskos D. Malliaros, Dimitrios M. Thilikos, and Michalis Vazirgiannis. 2014. CoreCluster: A Degeneracy Based Graph Clustering Framework. In AAAI Conference on Artificial Intelligence. 44--50."},{"key":"e_1_3_2_1_42_1","volume-title":"Characterization of Graphs Using Degree Cores. In International Workshop on Algorithms and Models for the Web-Graph (WAW)","volume":"4936","author":"Healy John","year":"2006","unstructured":"John Healy, Jeannette C. M. Janssen, Evangelos E. Milios, and William Aiello. 2006. Characterization of Graphs Using Degree Cores. In International Workshop on Algorithms and Models for the Web-Graph (WAW), Vol. 4936. 137--148."},{"key":"e_1_3_2_1_43_1","volume-title":"Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity. CoRR abs\/2002.10142","author":"Henzinger Monika","year":"2020","unstructured":"Monika Henzinger, Stefan Neumann, and Andreas Wiese. 2020. Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity. CoRR abs\/2002.10142 (2020), 18 pages."},{"key":"e_1_3_2_1_44_1","volume-title":"Revised Reprint","author":"Herlihy Maurice","unstructured":"Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming, Revised Reprint (1st ed.). Morgan Kaufmann Publishers Inc.","edition":"1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410463.3414657"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2960226"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00388-x"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2835441"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2017.151"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1746"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368300"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446099"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_3_2_1_58_1","unstructured":"Quanquan C. Liu Julian Shun and Igor Zablotchi. 2024. Parallel k-Core Decomposition with Batched Updates and Asynchronous Reads. arXiv:2401.08015 [cs.DC]"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep09602"},{"key":"e_1_3_2_1_60_1","volume-title":"Distributed Core Decomposition in Probabilistic Graphs. In International Conference on Computational Data and Social Networks (CSoNet)","volume":"11917","author":"Luo Qi","year":"2019","unstructured":"Qi Luo, Dongxiao Yu, Feng Li, Zhenhao Dou, Zhipeng Cai, Jiguo Yu, and Xiuzhen Cheng. 2019. Distributed Core Decomposition in Probabilistic Graphs. In International Conference on Computational Data and Social Networks (CSoNet), Vol. 11917. 16--32."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep19307"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_2_1_63_1","volume-title":"International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 1922--1924","author":"Medya Sourav","unstructured":"Sourav Medya, Tianyi Ma, Arlei Silva, and Ambuj K. Singh. 2020. A Game Theoretic Approach For k-Core Minimization. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 1922--1924."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2017.112"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01228509"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_3_2_1_68_1","first-page":"425","article-title":"Incremental k-core decomposition: algorithms and evaluation","volume":"25","author":"Sariy\u00fcce Ahmet Erdem","year":"2016","unstructured":"Ahmet Erdem Sariy\u00fcce, Bugra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and \u00dcmit V. \u00c7ataly\u00fcrek. 2016. Incremental k-core decomposition: algorithms and evaluation. Proceedings of the VLDB Endowment 25, 3 (2016), 425--447.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_1_69_1","volume-title":"Proceedings Seventh International Parallel Processing Symposium. 310--317","author":"Shen X.","unstructured":"X. Shen and W. Liang. 1993. A parallel algorithm for multiple edge updates of minimum spanning trees. In Proceedings Seventh International Parallel Processing Symposium. 310--317."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385416"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538584"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00030"},{"key":"e_1_3_2_1_73_1","volume-title":"Parallel Algorithm for Core Maintenance in Dynamic Graphs. In IEEE International Conference on Distributed Computing Systems (ICDCS). 2366--2371","author":"Wang Na","year":"2017","unstructured":"Na Wang, Dongxiao Yu, Hai Jin, Chen Qian, Xia Xie, and Qiang-Sheng Hua. 2017. Parallel Algorithm for Core Maintenance in Dynamic Graphs. In IEEE International Conference on Distributed Computing Systems (ICDCS). 2366--2371."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833070"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115406"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-009-0299-0"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.93"}],"event":{"name":"PPoPP '24: 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming","location":"Edinburgh United Kingdom","acronym":"PPoPP '24","sponsor":["SIGHPC ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing","SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627535.3638508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627535.3638508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:04Z","timestamp":1750287004000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627535.3638508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,20]]},"references-count":77,"alternative-id":["10.1145\/3627535.3638508","10.1145\/3627535"],"URL":"https:\/\/doi.org\/10.1145\/3627535.3638508","relation":{},"subject":[],"published":{"date-parts":[[2024,2,20]]},"assertion":[{"value":"2024-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}