Partitioning a large graph into multiple edge-balanced subgraphs by minimizing the number of cutting vertices (replication factor), plays a crucial role in distributed graph computing tasks. However, existing methods often overlook that vertex imbalance can also lead to workload imbalance, and their partitioning time becomes prohibitively long when the number of partitions is large. To address these issues, this paper investigates a dual-balanced edge partitioning problem, aiming to minimize the replication factor while satisfying both vertex and edge balance. We propose DEPL, a lightweight two-phase dual-balanced partitioner. In the first phase, vertices are grouped into clusters using a streaming clustering algorithm. In the second phase, the generated clusters are leveraged to assign edges by a partitioning strategy. Experimental results demonstrate that DEPL achieves better dual balance than state-of-the-art partitioners, while also maintaining a low replication factor. When the number of partitions is large, its runtime can be an order of magnitude lower than that of stateful streaming partitioners.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

DEPL: A Dual-Balanced Streaming Edge Partitioning in Linear Runtime

  • Mengna Wang,
  • Junchang Xin,
  • Xian Zhang,
  • Chenxi Yao,
  • Haoqi Wang,
  • Zhiqiong Wang

摘要

Partitioning a large graph into multiple edge-balanced subgraphs by minimizing the number of cutting vertices (replication factor), plays a crucial role in distributed graph computing tasks. However, existing methods often overlook that vertex imbalance can also lead to workload imbalance, and their partitioning time becomes prohibitively long when the number of partitions is large. To address these issues, this paper investigates a dual-balanced edge partitioning problem, aiming to minimize the replication factor while satisfying both vertex and edge balance. We propose DEPL, a lightweight two-phase dual-balanced partitioner. In the first phase, vertices are grouped into clusters using a streaming clustering algorithm. In the second phase, the generated clusters are leveraged to assign edges by a partitioning strategy. Experimental results demonstrate that DEPL achieves better dual balance than state-of-the-art partitioners, while also maintaining a low replication factor. When the number of partitions is large, its runtime can be an order of magnitude lower than that of stateful streaming partitioners.