Scalability and performance in distributed graph databases

doi:10.1007/s10586-026-06406-0

Return

Scalability and performance in distributed graph databases

2026-09-07

PRE

Oluwafemi Oloruntoba *

Deborah Olamide Oyeyemi

Adeyemi Adeesan Bamidele

Samuel O. Fakunle

Onyinyechi Gift Henry-Machame

DOI：10.1007/s10586-026-06406-0

Original

Original request for help

Save

Abstract

En 中文

Graph partitioning is a critical enabler of scalability in distributed graph databases, impacting load balancing, communication overhead, and query performance. This paper presents a comparative analysis of four partitioning strategies Random Vertex, Metis-based, Random Edge, and HDRF spanning both edge-cut and vertex-cut paradigms. Each approach is evaluated on synthetic and real-world datasets for metrics such as edge cut, replication factor, load balance, latency, and throughput. Our evaluation framework simulates distributed OLTP/OLAP query workloads on a prototype graph database cluster. Results show that while Metis achieves optimal partition quality for static, balanced graphs, HDRF provides superior performance and scalability for dynamic, power-law networks. The experiments reveal important trade-offs between partitioning complexity and runtime performance across different graph structures. This work contributes a scalable benchmarking environment, a set of representative partitioning algorithms, and statistically grounded insights to guide practitioners in choosing the appropriate strategy for specific workload and graph characteristics.

Keywords:

Graph partitioning

Distributed graph database

Vertex-cut

Edge-cut

Query performance

Scalability