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

摘要： 图划分在分布式处理大规模图数据中扮演着关键的角色。通过平衡节点的工作负载和通信成本，图划分方法提高了同构集群处理幂律图的效率。然而，在异构集群中节点计算能力和通信能力不一致，节点处理相同的时间成本不同的工作负载，最慢的节点系统成为瓶颈。为解决上述问题，异构感知流划分方法（SHAP）被提出。该方法采用One-pass流式邻域启发式划分策略，根据节点的性能来最小化分区间的图处理时间。通过复制因子分析，SHAP划分质量被证明具有理论上界。在一个具有4个真实世界图的异构集群中进行图处理算法实验。实验结果表明，SHAP与最先进的HDRF流划分算法比较，最高可以减少图算法时间11.37%，其复制因子仅为其0.47。

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