Combination of in-memory graph computation with mapreduce: A subgraph-centric method of pagerank

Qiuhong Li, Wei Wang, Peng Wang, Ke Dai, Zhihui Wang, Yang Wang, Weiwei Sun

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationWeb-Age Information Management - 14th International Conference, WAIM 2013, Proceedings
PublisherSpringer Verlag
Pages173-178
Number of pages6
ISBN (Print)9783642385612
DOIs
StatePublished - 2013
Externally publishedYes
Event14th International Conference on Web-Age Information Management, WAIM 2013 - Beidaihe, China
Duration: 14 Jun 201316 Jun 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7923 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Web-Age Information Management, WAIM 2013
Country/TerritoryChina
CityBeidaihe
Period14/06/1316/06/13

Fingerprint

Dive into the research topics of 'Combination of in-memory graph computation with mapreduce: A subgraph-centric method of pagerank'. Together they form a unique fingerprint.

Cite this