A Scalable Data Structure for Efficient Graph Analytics and In-Place Mutations
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).
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}
}
EUVIMED