关键词: 异构环境, 图划分, 分布式计算, 图计算, 数据管理

Abstract: Abstract: Graph partitioning plays a crucial role in the distributed processing of large-scale graph data. By balancing the workload and communication costs among nodes, graph partitioning methods improve the efficiency of processing power-law graphs in homogeneous clusters. However, in heterogeneous clusters, where nodes have inconsistent computational and communication abilities, The time cost of nodes processing the same workload is different, leading to the slowest node becoming a bottleneck in the system. To address this issue, a Heterogeneous Aware Stream Partitioning method (SHAP) has been proposed. This method employs a One-pass streaming neighborhood heuristic partitioning strategy to minimize inter-partition graph processing time based on node performance. Through replication factor analysis, the quality of SHAP partitioning is proven to have a theoretical upper bound. Graph algorithm experiments are conducted in a heterogeneous cluster with four real-world graphs. The experimental results show that SHAP can reduce the graph algorithm time by up to 11.37% compared to the state-of-the-art HDRF stream partitioning algorithm, with a replication factor that is only 0.47 of it.

Key words: heterogeneous environment, graph partitioning, distributed computing, graph computing, data management