A semi-clustering scheme for high performance PageRank on Hadoop

Seungtae Hong; Jeonghoon Lee; Jaewoo Chang; Dong Hoon Choi

doi:10.1007/978-3-319-12256-4_4

A semi-clustering scheme for high performance PageRank on Hadoop

Seungtae Hong
, Jeonghoon Lee
, Jaewoo Chang
, Dong Hoon Choi^*

^*Corresponding author for this work

Research output: Contribution to conference › Conference paper › peer-review

1 Scopus citations

Abstract

As global Internet business has been evolving, large-scale graphs are becoming popular. PageRank computation on the large-scale graphs using Hadoop with default data partitioning method suffers from poor performance because Hadoop scatters even a set of directly connected vertices to arbitrary multiple nodes. In this paper we propose a semi-clustering scheme to address this problem and improve the performance of PageRank on Hadoop. Our scheme divides a graph into a set of semi-clusters, each of which consists of connected vertices, and assigns a semi-cluster to a single data partition in order to reduce the cost of data exchange between nodes during the computation of PageRank. The semi-clusters are merged and split before the PageRank computation, in order to evenly distribute a large-scale graph into a number of data partitions. Our semi-clustering scheme drastically improves the performance: total elapsed time including the cost of the semi-clustering computation reduced by up to 36%. Furthermore, the effectiveness of our scheme increases as the size of the graph increases.

Original language	English
Title of host publication	Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings
Editors	Marta Indulska, Sandeep Purao
Publisher	Springer Verlag
Pages	35-44
Number of pages	10
ISBN (Electronic)	9783319122557
DOIs	https://doi.org/10.1007/978-3-319-12256-4_4
State	Published - 2014
Event	33rd International Conference on Conceptual Modeling, ER 2014 - Atlanta, United States Duration: 2014.10.27 → 2014.10.29

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8823
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	33rd International Conference on Conceptual Modeling, ER 2014
Country/Territory	United States
City	Atlanta
Period	14.10.27 → 14.10.29

Keywords

Hadoop
Large-scale graph analysis
PageRank
Semi-clustering

Quacquarelli Symonds(QS) Subject Topics

Computer Science & Information Systems

Access to Document

10.1007/978-3-319-12256-4_4

Cite this

Hong, S., Lee, J., Chang, J., & Choi, D. H. (2014). A semi-clustering scheme for high performance PageRank on Hadoop. In M. Indulska, & S. Purao (Eds.), Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings (pp. 35-44). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8823). Springer Verlag. https://doi.org/10.1007/978-3-319-12256-4_4

Hong, Seungtae ; Lee, Jeonghoon ; Chang, Jaewoo et al. / A semi-clustering scheme for high performance PageRank on Hadoop. Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings. editor / Marta Indulska ; Sandeep Purao. Springer Verlag, 2014. pp. 35-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8cbfdb4b1f8746cfa07443cd4bd3ad94,

title = "A semi-clustering scheme for high performance PageRank on Hadoop",

abstract = "As global Internet business has been evolving, large-scale graphs are becoming popular. PageRank computation on the large-scale graphs using Hadoop with default data partitioning method suffers from poor performance because Hadoop scatters even a set of directly connected vertices to arbitrary multiple nodes. In this paper we propose a semi-clustering scheme to address this problem and improve the performance of PageRank on Hadoop. Our scheme divides a graph into a set of semi-clusters, each of which consists of connected vertices, and assigns a semi-cluster to a single data partition in order to reduce the cost of data exchange between nodes during the computation of PageRank. The semi-clusters are merged and split before the PageRank computation, in order to evenly distribute a large-scale graph into a number of data partitions. Our semi-clustering scheme drastically improves the performance: total elapsed time including the cost of the semi-clustering computation reduced by up to 36\%. Furthermore, the effectiveness of our scheme increases as the size of the graph increases.",

keywords = "Hadoop, Large-scale graph analysis, PageRank, Semi-clustering",

author = "Seungtae Hong and Jeonghoon Lee and Jaewoo Chang and Choi, \{Dong Hoon\}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 33rd International Conference on Conceptual Modeling, ER 2014 ; Conference date: 27-10-2014 Through 29-10-2014",

year = "2014",

doi = "10.1007/978-3-319-12256-4\_4",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "35--44",

editor = "Marta Indulska and Sandeep Purao",

booktitle = "Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings",

}

Hong, S, Lee, J, Chang, J & Choi, DH 2014, A semi-clustering scheme for high performance PageRank on Hadoop. in M Indulska & S Purao (eds), Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8823, Springer Verlag, pp. 35-44, 33rd International Conference on Conceptual Modeling, ER 2014, Atlanta, United States, 14.10.27. https://doi.org/10.1007/978-3-319-12256-4_4

A semi-clustering scheme for high performance PageRank on Hadoop. / Hong, Seungtae; Lee, Jeonghoon; Chang, Jaewoo et al.
Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings. ed. / Marta Indulska; Sandeep Purao. Springer Verlag, 2014. p. 35-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8823).

Research output: Contribution to conference › Conference paper › peer-review

TY - GEN

T1 - A semi-clustering scheme for high performance PageRank on Hadoop

AU - Hong, Seungtae

AU - Lee, Jeonghoon

AU - Chang, Jaewoo

AU - Choi, Dong Hoon

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - As global Internet business has been evolving, large-scale graphs are becoming popular. PageRank computation on the large-scale graphs using Hadoop with default data partitioning method suffers from poor performance because Hadoop scatters even a set of directly connected vertices to arbitrary multiple nodes. In this paper we propose a semi-clustering scheme to address this problem and improve the performance of PageRank on Hadoop. Our scheme divides a graph into a set of semi-clusters, each of which consists of connected vertices, and assigns a semi-cluster to a single data partition in order to reduce the cost of data exchange between nodes during the computation of PageRank. The semi-clusters are merged and split before the PageRank computation, in order to evenly distribute a large-scale graph into a number of data partitions. Our semi-clustering scheme drastically improves the performance: total elapsed time including the cost of the semi-clustering computation reduced by up to 36%. Furthermore, the effectiveness of our scheme increases as the size of the graph increases.

AB - As global Internet business has been evolving, large-scale graphs are becoming popular. PageRank computation on the large-scale graphs using Hadoop with default data partitioning method suffers from poor performance because Hadoop scatters even a set of directly connected vertices to arbitrary multiple nodes. In this paper we propose a semi-clustering scheme to address this problem and improve the performance of PageRank on Hadoop. Our scheme divides a graph into a set of semi-clusters, each of which consists of connected vertices, and assigns a semi-cluster to a single data partition in order to reduce the cost of data exchange between nodes during the computation of PageRank. The semi-clusters are merged and split before the PageRank computation, in order to evenly distribute a large-scale graph into a number of data partitions. Our semi-clustering scheme drastically improves the performance: total elapsed time including the cost of the semi-clustering computation reduced by up to 36%. Furthermore, the effectiveness of our scheme increases as the size of the graph increases.

KW - Hadoop

KW - Large-scale graph analysis

KW - PageRank

KW - Semi-clustering

UR - https://www.scopus.com/pages/publications/84910612262

U2 - 10.1007/978-3-319-12256-4_4

DO - 10.1007/978-3-319-12256-4_4

M3 - Conference paper

AN - SCOPUS:84910612262

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 35

EP - 44

BT - Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings

A2 - Indulska, Marta

A2 - Purao, Sandeep

PB - Springer Verlag

T2 - 33rd International Conference on Conceptual Modeling, ER 2014

Y2 - 27 October 2014 through 29 October 2014

ER -

Hong S, Lee J, Chang J, Choi DH. A semi-clustering scheme for high performance PageRank on Hadoop. In Indulska M, Purao S, editors, Advances in Conceptual Modeling - ER 2014 Workshops, ENMO, MoBiD, MReBA, QMMQ, SeCoGIS, WISM, and ER Demos, Proceedings. Springer Verlag. 2014. p. 35-44. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-12256-4_4

A semi-clustering scheme for high performance PageRank on Hadoop

Abstract

Publication series

Conference

Keywords

Quacquarelli Symonds(QS) Subject Topics

Access to Document

Other files and links

Fingerprint

Cite this