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
Go to the corresponding LIPIcs Volume Portal

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

LIPIcs-OPODIS-2020-17.pdf (0.6 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI