TY - GEN
T1 - Combination of in-memory graph computation with mapreduce
T2 - 14th International Conference on Web-Age Information Management, WAIM 2013
AU - Li, Qiuhong
AU - Wang, Wei
AU - Wang, Peng
AU - Dai, Ke
AU - Wang, Zhihui
AU - Wang, Yang
AU - Sun, Weiwei
PY - 2013
Y1 - 2013
N2 - In order to improve the efficiency of the PageRank algorithm, parallelizing methods, especially the ones based on MapReduce, interest many researchers during the past several years. Previous implementations of the PageRank algorithm on MapReduce ignore the characteristic of locality in distributed systems which is very important to reduce the I/O and network costs. In this paper, we explore the locality property and propose a new method for fast PageRank computation by supporting a subgraph as an input record for map functions. Graph partitioning techniques and a message grouping method are employed to guarantee the efficiency of communication among different subgraphs. Experiments show that our method is significantly more efficient than previous approaches without accuracy loss. The key idea to change the granularity of basic processing units from edges to subgraphs can benefit many other parallelizing algorithms for graph processing.
AB - In order to improve the efficiency of the PageRank algorithm, parallelizing methods, especially the ones based on MapReduce, interest many researchers during the past several years. Previous implementations of the PageRank algorithm on MapReduce ignore the characteristic of locality in distributed systems which is very important to reduce the I/O and network costs. In this paper, we explore the locality property and propose a new method for fast PageRank computation by supporting a subgraph as an input record for map functions. Graph partitioning techniques and a message grouping method are employed to guarantee the efficiency of communication among different subgraphs. Experiments show that our method is significantly more efficient than previous approaches without accuracy loss. The key idea to change the granularity of basic processing units from edges to subgraphs can benefit many other parallelizing algorithms for graph processing.
UR - http://www.scopus.com/inward/record.url?scp=84879996890&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38562-9_18
DO - 10.1007/978-3-642-38562-9_18
M3 - Conference contribution
AN - SCOPUS:84879996890
SN - 9783642385612
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 173
EP - 178
BT - Web-Age Information Management - 14th International Conference, WAIM 2013, Proceedings
PB - Springer Verlag
Y2 - 14 June 2013 through 16 June 2013
ER -