DSP-CC: I/O Efficient Parallel Computation of Connected Components in Billion-scale Networks (Extended Abstract)
- DSP-CC: I/O Efficient Parallel Computation of Connected Components in Billion-scale Networks (Extended Abstract)
- Min-Soo Kim; Sangyeon Lee; Han, WS; Himchan Park; Jeong-Hoon Lee
- Date Issued
- Computing connected components (CC) is a core operation on graph data. Since billion-scale graphs cannot be resident in memory of a single machine, there have been proposed a number of distributed graph processing methods. The representative ones for CC are Hash-To-Min and PowerGraph. Hash-To-Min focuses on minimizing the number of MapReduce rounds, but is still slower than in-memory methods, PowerGraph is a fast and general in-memory graph method, but requires a lot of machines for handling billion-scale graphs. We propose an ultra-fast parallel method DSP-CC, using only a single PC that exploits secondary storage like a PCI-E SSD for handling billion-scale graphs. It can compute connected components I/O efficiently using only a limited size of memory. Our experimental results show that DSP-CC significantly outperforms the representative methods including Hash-To-Min and PowerGraph.
- Article Type
- Proceedings - International Conference on Data Engineering, page. 1504 - 1505, 2016-05
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.