DSP-CC: I/O Efficient Parallel Computation of Connected Components in Billion-scale Networks (Extended Abstract)
SCIE
SCOPUS
- Title
- DSP-CC: I/O Efficient Parallel Computation of Connected Components in Billion-scale Networks (Extended Abstract)
- Authors
- Min-Soo Kim; Sangyeon Lee; Han, WS; Himchan Park; Jeong-Hoon Lee
- Date Issued
- 2016-05
- Publisher
- IEEE
- Abstract
- 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.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/38242
- DOI
- 10.1109/ICDE.2016.7498396
- ISSN
- 1084-4627
- Article Type
- Article
- Citation
- 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.