.png){kind=icon}
.png){kind=icon}
Return
3-D Partitioning for Large-Scale Graph Processing
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2020.2986736.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Disk I/O is the major performance bottleneck of existing out-of-core graph processing systems. We found that the total I/O amount can be reduced by loading more vertices into memory every time. Although task partitioning of a graph processing system is traditionally considered equivalent to the graph partition problem, this assumption is untrue for many Machine Learning and Data Mining (MLDM) problems: instead of a single value, a vector of data elements is defined as the property for each vertex/edge. By dividing each vertex into multiple sub-vertices, more vertices can be loaded into memory every time, leading to less amount of disk I/O. To explore this new opportunity, we propose a category of 3-D partitioning algorithm that considers the hidden dimension to partition the property vector. The 3-D partitioning algorithm provides a new tradeoff to reduce communication costs, which is adaptive to both distributed and out-of-core scenarios. Based on it, we build a distributed graph processing system CubeSingleCube. Since network traffic is significantly reduced, Cube outperforms state-of-the-art graph-parallel system PowerLyra by up to 4.7x. By largely reducing the disk I/O amount, the performance of SingleCube is significantly better than state-of-the-art out-of-core system GridGraph (up to 4.5x).
Keywords:
Partitioning algorithms
Task analysis
Programming
Loading
Memory management
Microsoft Windows
Computational efficiency
Graph processing
task partitioning
distributed systems
disk I/O
big data
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K