2026-07-23T05:50:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13502 2024-03-06T10:52:13Z ddc:004 open_access

CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure Firmli, Soukaina Trigonakis, Vasileios Lozi, Jean-Pierre Psaroudakis, Iraklis Weld, Alexander Chiadmi, Dalila Hong, Sungpack Chafi, Hassan Data Structures Concurrency Graph Processing Graph Mutations The graph model enables a broad range of analysis, thus graph processing is an invaluable tool in data analytics. At the heart of every graph-processing system lies a concurrent graph data structure storing the graph. Such a data structure needs to be highly efficient for both graph algorithms and queries. Due to the continuous evolution, the sparsity, and the scale-free nature of real-world graphs, graph-processing systems face the challenge of providing an appropriate graph data structure that enables both fast analytical workloads and low-memory graph mutations. Existing graph structures offer a hard trade-off between read-only performance, update friendliness, and memory consumption upon updates. In this paper, we introduce CSR++, a new graph data structure that removes these trade-offs and enables both fast read-only analytics and quick and memory-friendly mutations. CSR++ combines ideas from CSR, the fastest read-only data structure, and adjacency lists to achieve the best of both worlds. We compare CSR++ to CSR, adjacency lists from the Boost Graph Library, and LLAMA, a state-of-the-art update-friendly graph structure. In our evaluation, which is based on popular graph-processing algorithms executed over real-world graphs, we show that CSR++ remains close to CSR in read-only concurrent performance (within 10% on average), while significantly outperforming CSR (by an order of magnitude) and LLAMA (by almost 2×) with frequent updates. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Soukaina Firmli and Vasileios Trigonakis and Jean-Pierre Lozi and Iraklis Psaroudakis and Alexander Weld and Dalila Chiadmi and Sungpack Hong and Hassan Chafi 2021 Is Part Of LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2020.17 urn:nbn:de:0030-drops-135021 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.17 eng https://creativecommons.org/licenses/by/3.0/legalcode