An algorithm to improve MPI-PageRank performance by reducing synchronization time

© 2015 IEEE. Ranking is an important operation in web searching. Among many ranking algorithms, PageRank is a most notable one. However, sequential PageRank computing on a large web-link graph is not efficient. To address such limitation, parallel PageRank implemented on Message Passing Interface (M...

Full description

Saved in:
Bibliographic Details
Main Authors: Sangamuang S., Boonma P., Kyii L.
Format: Conference Proceeding
Published: 2017
Online Access:https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84964403091&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/42092
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Chiang Mai University
id th-cmuir.6653943832-42092
record_format dspace
spelling th-cmuir.6653943832-420922017-09-28T04:25:12Z An algorithm to improve MPI-PageRank performance by reducing synchronization time Sangamuang S. Boonma P. Kyii L. © 2015 IEEE. Ranking is an important operation in web searching. Among many ranking algorithms, PageRank is a most notable one. However, sequential PageRank computing on a large web-link graph is not efficient. To address such limitation, parallel PageRank implemented on Message Passing Interface (MPI) is a viable choice. Generally speaking, MPI-PageRank will be implemented using a root node and many computing, i.e., child, nodes. In each PageRank iteration, root node will partition web-link graph and distribute to child nodes. Then, each child node will perform PageRank on its partial web-link graph. Next, child nodes will send the result back to be combined at the root node. This operation will be performed iteratively before the ranking is converged. From the observation that when the number of nodes increase, the time to communicate between root and child nodes, i.e., synchronization time, increases rapidly such that it overcomes the benefit of parallel computing. This paper proposed an algorithm to reduce such time with a trade-off on ranking accuracy. The evaluation result show that the proposed algorithm can improve performance in term of the execution time with a bargain of accuracy. 2017-09-28T04:25:12Z 2017-09-28T04:25:12Z 2016-02-08 Conference Proceeding 2-s2.0-84964403091 10.1109/ICSEC.2015.7401454 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84964403091&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/42092
institution Chiang Mai University
building Chiang Mai University Library
country Thailand
collection CMU Intellectual Repository
description © 2015 IEEE. Ranking is an important operation in web searching. Among many ranking algorithms, PageRank is a most notable one. However, sequential PageRank computing on a large web-link graph is not efficient. To address such limitation, parallel PageRank implemented on Message Passing Interface (MPI) is a viable choice. Generally speaking, MPI-PageRank will be implemented using a root node and many computing, i.e., child, nodes. In each PageRank iteration, root node will partition web-link graph and distribute to child nodes. Then, each child node will perform PageRank on its partial web-link graph. Next, child nodes will send the result back to be combined at the root node. This operation will be performed iteratively before the ranking is converged. From the observation that when the number of nodes increase, the time to communicate between root and child nodes, i.e., synchronization time, increases rapidly such that it overcomes the benefit of parallel computing. This paper proposed an algorithm to reduce such time with a trade-off on ranking accuracy. The evaluation result show that the proposed algorithm can improve performance in term of the execution time with a bargain of accuracy.
format Conference Proceeding
author Sangamuang S.
Boonma P.
Kyii L.
spellingShingle Sangamuang S.
Boonma P.
Kyii L.
An algorithm to improve MPI-PageRank performance by reducing synchronization time
author_facet Sangamuang S.
Boonma P.
Kyii L.
author_sort Sangamuang S.
title An algorithm to improve MPI-PageRank performance by reducing synchronization time
title_short An algorithm to improve MPI-PageRank performance by reducing synchronization time
title_full An algorithm to improve MPI-PageRank performance by reducing synchronization time
title_fullStr An algorithm to improve MPI-PageRank performance by reducing synchronization time
title_full_unstemmed An algorithm to improve MPI-PageRank performance by reducing synchronization time
title_sort algorithm to improve mpi-pagerank performance by reducing synchronization time
publishDate 2017
url https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84964403091&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/42092
_version_ 1681422123883560960