1 Search Results for "Trigonakis, Vasileios"

Document
DOI: 10.4230/LIPIcs.OPODIS.2020.17
CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure

Authors: Soukaina Firmli, Vasileios Trigonakis, Jean-Pierre Lozi, Iraklis Psaroudakis, Alexander Weld, Dalila Chiadmi, Sungpack Hong, and Hassan Chafi

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

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.
Cite as

Soukaina Firmli, Vasileios Trigonakis, Jean-Pierre Lozi, Iraklis Psaroudakis, Alexander Weld, Dalila Chiadmi, Sungpack Hong, and Hassan Chafi. CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{firmli_et_al:LIPIcs.OPODIS.2020.17,
  author =	{Firmli, Soukaina and Trigonakis, Vasileios and Lozi, Jean-Pierre and Psaroudakis, Iraklis and Weld, Alexander and Chiadmi, Dalila and Hong, Sungpack and Chafi, Hassan},
  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 =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.17},
  URN =		{urn:nbn:de:0030-drops-135021},
  doi =		{10.4230/LIPIcs.OPODIS.2020.17},
  annote =	{Keywords: Data Structures, Concurrency, Graph Processing, Graph Mutations}
}
  • Refine by Author
  • 1 Chafi, Hassan
  • 1 Chiadmi, Dalila
  • 1 Firmli, Soukaina
  • 1 Hong, Sungpack
  • 1 Lozi, Jean-Pierre
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Information systems → Data structures
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Concurrency
  • 1 Data Structures
  • 1 Graph Mutations
  • 1 Graph Processing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact