EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Scalable Data Structure for Efficient Graph Analytics and In-Place Mutations

Soukaina Firmli, Dalila Chiadmi

Data · 03.11.2023 · 8 (11) · 166

DOI: 10.3390/data8110166 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Data, online erschienen am 03.11.2023. Verfasst von Soukaina Firmli und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 60 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The graph model enables a broad range of analyses; thus, graph processing (GP) is an invaluable tool in data analytics. At the heart of every GP system lies a concurrent graph data structure that stores 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, GP systems face the challenge of providing an appropriate graph data structure that enables both fast analytical workloads and fast, low-memory graph mutations. Existing graph structures offer a hard tradeoff among read-only performance, update friendliness, and memory consumption upon updates. In this paper, we introduce CSR++, a new graph data structure that removes these tradeoffs 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 (ALs) to achieve the best of both worlds. We compare CSR++ to CSR, ALs from the Boost Graph Library (BGL), and the following state-of-the-art update-friendly graph structures: LLAMA, STINGER, GraphOne, and Teseo. In our evaluation, which is based on popular GP 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. We also show that both CSR++’s update throughput and analytics performance exceed those of several state-of-the-art graph structures while maintaining low memory consumption when the workload includes updates.

Zitieren

APA

Firmli, S., & Chiadmi, D. (2023). A Scalable Data Structure for Efficient Graph Analytics and In-Place Mutations. Data, 8(11), 166. https://doi.org/10.3390/data8110166

Vancouver

Firmli S, Chiadmi D. A Scalable Data Structure for Efficient Graph Analytics and In-Place Mutations. Data. 2023;8(11):166. doi:10.3390/data8110166

BibTeX
@article{Firmli2023,
  author = {Firmli, Soukaina and Chiadmi, Dalila},
  title = {A Scalable Data Structure for Efficient Graph Analytics and In-Place Mutations},
  journal = {Data},
  year = {2023},
  volume = {8},
  number = {11},
  pages = {166},
  doi = {10.3390/data8110166}
}
Kostenlos starten →