{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:12:28Z","timestamp":1779174748536,"version":"3.51.4"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-2144547"],"award-info":[{"award-number":["IIS-2144547"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Large-scale graph analytics has become increasingly common in areas like social networks, physical sciences, transportation networks, and recommendation systems. Since many such practical graphs do not fit in main memory, graph analytics performance depends on efficiently utilizing underlying storage devices. These out-of-core graph processing systems employ sharding and sub-graph partitioning to optimize for storage while relying on efficient sequential access of traditional hard disks. However, today's storage is increasingly based on solid-state drives (SSDs) that exhibit high internal parallelism and efficient random accesses. Yet, state-of-the-art graph processing systems do not explicitly exploit those properties, resulting in subpar performance.<\/jats:p>\n          <jats:p>In this paper, we develop CAVE, the first graph processing engine that optimally exploits underlying SSD-based storage by harnessing the available storage device parallelism via carefully selecting which I\/Os to graph data can be issued concurrently. Thus, CAVE traverses multiple paths and processes multiple nodes and edges concurrently, achieving parallelization at a granular level. We identify two key ways to parallelize graph traversal algorithms based on the graph structure and algorithm: intra-subgraph and inter-subgraph parallelization. The first identifies subgraphs that contain vertices that can be accessed in parallel, while the latter identifies subgraphs that can be processed in their entirety in parallel. To showcase the benefit of our approach, we build within CAVE parallelized versions of five popular graph algorithms (Breadth-First Search, Depth-First Search, Weakly Connected Components, PageRank, Random Walk) that exploit the full bandwidth of the underlying device. CAVE uses a blocked file format based on adjacency lists and employs a concurrent cache pool that is essential to the parallelization of graph algorithms. By experimenting with different types of graphs on three SSD devices, we demonstrate that CAVE utilizes the available parallelism, and scales to diverse real-world graph datasets. CAVE achieves up to one order of magnitude speedup compared to the popular out-of-core systems Mosaic and GridGraph, and up to three orders of magnitude speedup in runtime compared to GraphChi.<\/jats:p>","DOI":"10.1145\/3654928","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":10,"title":["CAVE: Concurrency-Aware Graph Processing on SSDs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0926-8316","authenticated-orcid":false,"given":"Tarikul Islam","family":"Papon","sequence":"first","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8252-2096","authenticated-orcid":false,"given":"Taishan","family":"Chen","sequence":"additional","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6924-6658","authenticated-orcid":false,"given":"Shuo","family":"Zhang","sequence":"additional","affiliation":[{"name":"Columbia University, New York City, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1837-0010","authenticated-orcid":false,"given":"Manos","family":"Athanassoulis","sequence":"additional","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807651"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/S13278-022-00862--3"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC). 57--70","author":"Agrawal Nitin","year":"2008","unstructured":"Nitin Agrawal, Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, and Rina Panigrahy. 2008. Design Tradeoffs for SSD Performance. In Proceedings of the USENIX Annual Technical Conference (ATC). 57--70. http:\/\/dl.acm.org\/citation.cfm?id=1404019"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/933363"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS). 23--32","author":"Athanassoulis Manos","unstructured":"Manos Athanassoulis, Bishwaranjan Bhattacharjee, Mustafa Canim, and Kenneth A. Ross. 2012. Path Processing using Solid State Storage. In Proceedings of the International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS). 23--32. http:\/\/www.adms-conf.org\/athanassoulis_adms12.pdf"},{"key":"e_1_2_2_6_1","volume-title":"Zichen Zhu, and Dimitris Staratzis.","author":"Athanassoulis Manos","year":"2022","unstructured":"Manos Athanassoulis, Subhadeep Sarkar, Tarikul Islam Papon, Zichen Zhu, and Dimitris Staratzis. 2022. Building Deletion-Compliant Data Systems. In IEEE Data Engineering Bulletin. 21--36."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169--7552(98)00110-X"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818376"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2011.5749735"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3298989"},{"key":"e_1_2_2_11_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press. http:\/\/mitpress.mit.edu\/books\/introduction-algorithms","edition":"3"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430926"},{"key":"e_1_2_2_13_1","volume-title":"Graph Algorithms","author":"Even Shimon","unstructured":"Shimon Even and Guy Even. 2012. Graph Algorithms (2nd ed.). Cambridge University Press. http:\/\/www.cambridge.org\/us\/academic\/subjects\/computer-science\/algorithmics-complexity-computer-algebra-and-computational-g\/graph-algorithms-2nd-edition","edition":"2"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 17--30","author":"Gonzalez Joseph E","year":"2012","unstructured":"Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 17--30. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/gonzalez"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 599--613","author":"Gonzalez Joseph E","year":"2014","unstructured":"Joseph E Gonzalez, Reynold S Xin, Ankur Dave, Daniel Crankshaw, Michael J Franklin, and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 599--613. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/gonzalez"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487581"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007270"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3538643.3539757"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR). https:\/\/www.cidrdb.org\/cidr2023\/papers\/p48-jin.pdf","author":"Jin Guodong","year":"2023","unstructured":"Guodong Jin, Xiyang Feng, Ziyi Chen, Chang Liu, and Semih Salihoglu. 2023. K\u00d9 ZU Graph Database Management System. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). https:\/\/www.cidrdb.org\/cidr2023\/papers\/p48-jin.pdf"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176887.1176911"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020580"},{"key":"e_1_2_2_22_1","volume-title":"The Art of Computer Programming","author":"Knuth Donald E.","year":"2022","unstructured":"Donald E. Knuth. 2022. \"Weak components\", The Art of Computer Programming, Volume IV, Pre-Fascicle 12A: Components and Traversal. 11--14 pages. https:\/\/cs.stanford.edu\/ knuth\/fasc12a.pdf"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196915"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 31--46","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy E Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-Scale Graph Computation on Just a PC. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 31--46. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/kyrola"},{"key":"e_1_2_2_25_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_26_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 285--300","author":"Liu Hang","year":"2017","unstructured":"Hang Liu and H Howie Huang. 2017. Graphene: Fine-Grained IO Management for Graph Computing. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 285--300. https:\/\/www.usenix.org\/conference\/fast17\/technical-sessions\/presentation\/liu"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1631\/FITEE.1900127"},{"key":"e_1_2_2_28_1","volume-title":"Paul erdos is eighty","author":"L\u00e1szl\u00f3 Lov\u00e1","year":"1993","unstructured":"L\u00e1szl\u00f3 Lov\u00e1 sz. 1993. Random walks on graphs. Combinatorics, Paul erdos is eighty, Vol. 2, 1--46 (1993), 4."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2017.2697961"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322275"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.23919\/DATE54114.2022.9774677"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00454"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466003"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR).","author":"Papon Tarikul Islam","year":"2021","unstructured":"Tarikul Islam Papon and Manos Athanassoulis. 2021b. The Need for a New I\/O Model. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR)."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00106"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTR.2009.5289148"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 13","author":"Park Stan","year":"2012","unstructured":"Stan Park and Kai Shen. 2012. FIOS: a fair, efficient flash I\/O scheduler. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 13."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.34"},{"key":"e_1_2_2_43_1","volume-title":"The Parallel Hashmap. https:\/\/github.com\/greg7mdp\/parallel-hashmap","author":"Popovitch Gregory","year":"2020","unstructured":"Gregory Popovitch. 2020. The Parallel Hashmap. https:\/\/github.com\/greg7mdp\/parallel-hashmap (2020)."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389757"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.2172\/1372902"},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC). 67--78","author":"Shen Kai","year":"2013","unstructured":"Kai Shen and Stan Park. 2013. FlashFQ: A Fair Queueing I\/O Scheduler for Flash-Based SSDs. In Proceedings of the USENIX Annual Technical Conference (ATC). 67--78."},{"key":"e_1_2_2_49_1","volume-title":"a fast, lightweight, and easy-to-use C17 thread pool library. https:\/\/github.com\/bshoshany\/thread-pool","author":"Shoshany Barak","year":"2021","unstructured":"Barak Shoshany. 2021. BS::thread_pool: a fast, lightweight, and easy-to-use C17 thread pool library. https:\/\/github.com\/bshoshany\/thread-pool (2021)."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037744"},{"key":"e_1_2_2_53_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 763--782","author":"Wang Kai","year":"2018","unstructured":"Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018. RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 763--782. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/wang"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/630"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556581"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688507"},{"key":"e_1_2_2_58_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC). 441--452","author":"Zhang Yu","year":"2018","unstructured":"Yu Zhang, Xiaofei Liao, Hai Jin, Lin Gu, Ligang He, Bingsheng He, and Haikun Liu. 2018. CGraph: A Correlations-aware Approach for Efficient Concurrent Iterative Graph Processing. In Proceedings of the USENIX Annual Technical Conference (ATC). 441--452. https:\/\/www.usenix.org\/conference\/atc18\/presentation\/zhang-yu"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_2_60_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 45--58","author":"Zheng Da","year":"2015","unstructured":"Da Zheng, Disa Mhembere, Randal C Burns, Joshua T Vogelstein, Carey E Priebe, and Alexander S Szalay. 2015. FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 45--58. https:\/\/www.usenix.org\/conference\/fast15\/technical-sessions\/presentation\/zheng"},{"key":"e_1_2_2_61_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 301--316","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A Computation-Centric Distributed Graph Processing System. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 301--316. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/zhu"},{"key":"e_1_2_2_62_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC). 375--386","author":"Zhu Xiaowei","year":"2015","unstructured":"Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. In Proceedings of the USENIX Annual Technical Conference (ATC). 375--386. https:\/\/www.usenix.org\/conference\/atc15\/technical-session\/presentation\/zhu"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00283"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654928","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:42:03Z","timestamp":1755787323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654928"],"URL":"https:\/\/doi.org\/10.1145\/3654928","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}