Cited 0 time in webofscience Cited 0 time in scopus

DSP-CC: I/O efficient parallel computation of connected components in billion-scale networks

Title
DSP-CC: I/O efficient parallel computation of connected components in billion-scale networks
Authors
Kim, Min-SooLee, SangyeonHan, Wook-ShinPark, HimchanLee, Jeong-Hoon
DGIST Authors
Kim, Min-Soo; Park, Himchan
Issue Date
2016
Citation
32nd IEEE International Conference on Data Engineering, ICDE 2016, 1504-1505
Type
Conference
Article Type
Conference Paper
ISBN
9780000000000
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. © 2016 IEEE.
URI
http://hdl.handle.net/20.500.11750/3645
DOI
10.1109/ICDE.2016.7498396
Publisher
Institute of Electrical and Electronics Engineers Inc.
Related Researcher
Files:
There are no files associated with this item.
Collection:
Information and Communication EngineeringETC2. Conference Papers


qrcode mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE