PACC: Large scale connected component computation on Hadoop and Spark

Cited 4 time in webofscience Cited 2 time in scopus
  • Hit : 647
  • Download : 86
A connected component in a graph is a set of nodes linked to each other by paths. The problem of finding connected components has been applied to diverse graph analysis tasks such as graph partitioning, graph compression, and pattern recognition. Several distributed algorithms have been proposed to find connected components in enormous graphs. Ironically, the distributed algorithms do not scale enough due to unnecessary data IO & processing, massive intermediate data, numerous rounds of computations, and load balancing issues. In this paper, we propose a fast and scalable distributed algorithm PACC (PartitionAware Connected Components) for connected component computation based on three key techniques: two-step processing of partitioning & computation, edge filtering, and sketching. PACC considerably shrinks the size of intermediate data, the size of input graph, and the number of rounds without suffering from load balancing issues. PACC performs 2.9 to 10.7 times faster on real-world graphs compared to the state-of-the-art MapReduce and Spark algorithms.
Publisher
PUBLIC LIBRARY SCIENCE
Issue Date
2020-03
Language
English
Article Type
Article
Citation

PLOS ONE, v.15, no.3

ISSN
1932-6203
DOI
10.1371/journal.pone.0229936
URI
http://hdl.handle.net/10203/274779
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
PACC-Large-scale-connected-component-computatio...(1.1 MB)Download
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 4 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0