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. |
Year | DOI | Venue |
---|---|---|
2020 | 10.4230/LIPIcs.OPODIS.2020.17 | OPODIS |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 8 |
Name | Order | Citations | PageRank |
---|---|---|---|
Soukaina Firmli | 1 | 0 | 0.34 |
Vasileios Trigonakis | 2 | 0 | 0.34 |
Jean-Pierre Lozi | 3 | 111 | 7.13 |
Iraklis Psaroudakis | 4 | 0 | 0.34 |
Alexander Weld | 5 | 0 | 0.34 |
Dalila Chiadmi | 6 | 0 | 0.34 |
Sungpack Hong | 7 | 0 | 0.34 |
Hassan Chafi | 8 | 0 | 0.34 |