License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.17
URN: urn:nbn:de:0030-drops-135021
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13502/
Firmli, Soukaina ;
Trigonakis, Vasileios ;
Lozi, Jean-Pierre ;
Psaroudakis, Iraklis ;
Weld, Alexander ;
Chiadmi, Dalila ;
Hong, Sungpack ;
Chafi, Hassan
CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure
Abstract
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.
BibTeX - Entry
@InProceedings{firmli_et_al:LIPIcs:2021:13502,
author = {Soukaina Firmli and Vasileios Trigonakis and Jean-Pierre Lozi and Iraklis Psaroudakis and Alexander Weld and Dalila Chiadmi and Sungpack Hong and Hassan Chafi},
title = {{CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure}},
booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
pages = {17:1--17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-176-4},
ISSN = {1868-8969},
year = {2021},
volume = {184},
editor = {Quentin Bramas and Rotem Oshman and Paolo Romano},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13502},
URN = {urn:nbn:de:0030-drops-135021},
doi = {10.4230/LIPIcs.OPODIS.2020.17},
annote = {Keywords: Data Structures, Concurrency, Graph Processing, Graph Mutations}
}
|
Keywords: |
|
Data Structures, Concurrency, Graph Processing, Graph Mutations |
|
Collection: |
|
24th International Conference on Principles of Distributed Systems (OPODIS 2020) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
25.01.2021 |
