EUVIMEDEUVIMED entdecken
Crossref

Bw-Graph: An Efficient Graph Storage System Harmonizing Topology-Aware Tree with Paged CSR

Songyao Wang, Chaokun Wang, Zecheng Li, Aoqi Zhang

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27

DOI: 10.1145/3802025 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Songyao Wang und 3 weiteren Autor:innen. Die Arbeit nennt 62 Literaturangaben. Gefördert von: the National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

As digital transformation accelerates, modern graph datasets routinely scale to billions of vertices and edges, demanding storage systems that simultaneously support dynamic updates, rapid neighbor retrieval, and high-performance analytics. However, existing systems face significant performance bottlenecks. While LSM-Tree-based approaches have gained popularity for their write efficiency, they suffer from fundamental read amplification problems that remain unresolved despite various optimization attempts. Moreover, most systems organize data by vertex IDs for simplicity, thereby sacrificing topological locality that could benefit graph algorithms. Although recent topology-aware methods offer improvements, they suffer from severe partition imbalance and fragility under updates. These challenges are further compounded by concurrency control designs in which structural modification operations block user requests, thereby limiting system throughput. To address these challenges, we present Bw-Graph, a graph storage system that harmonizes a Topology-Aware Tree with Paged CSR. Bw-Graph employs CSR pages for efficient neighbor access, while utilizing append-only Δ Pages to enable sequential writes to subgraphs. To enable efficient graph analytics, we propose a Topology-Aware Tree that hierarchically organizes graph data to co-locate densely connected vertices in contiguous physical storage. The underlying weight-constrained graph partitioning scheme ensures balanced partition sizes while preserving topological locality. To support high concurrency, we develop a tailored MVCC mechanism that leverages the append-only nature of Δ Pages for lightweight version management, and exploits a multi-version vertex index to guarantee consistency without blocking user requests during structural modification operations. Comprehensive evaluations demonstrate that Bw-Graph achieves significant performance improvements across diverse workloads. For analytics tasks, Bw-Graph further delivers performance comparable to that of dedicated graph processing systems (e.g., GridGraph).

Förderung

  • the National Natural Science Foundation of China

Zitieren

APA

Wang, S., Wang, C., Li, Z., & Zhang, A. (2026). Bw-Graph: An Efficient Graph Storage System Harmonizing Topology-Aware Tree with Paged CSR. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802025

Vancouver

Wang S, Wang C, Li Z, Zhang A. Bw-Graph: An Efficient Graph Storage System Harmonizing Topology-Aware Tree with Paged CSR. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802025

BibTeX
@article{Wang2026,
  author = {Wang, Songyao and Wang, Chaokun and Li, Zecheng and Zhang, Aoqi},
  title = {Bw-Graph: An Efficient Graph Storage System Harmonizing Topology-Aware Tree with Paged CSR},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--27},
  doi = {10.1145/3802025}
}
Kostenlos starten →