Scalable big graph processing in MapReduce

Qin, L; Yu, JX; Chang, L; Cheng, H; Zhang, C; Lin, X

Scalable big graph processing in MapReduce

Qin, L

Yu, JX

Chang, L Cheng, H Zhang, C

Lin, X

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, pp. 827 - 838
Issue Date:: 2014-01-01

Closed Access

	Filename	Description	Size
	[2014 SIGMOD] Scalable Big Graph Processing in MapReduce.pdf	Published version	511.06 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.contributor.author	Chang, L	en_US
dc.contributor.author	Cheng, H	en_US
dc.contributor.author	Zhang, C https://orcid.org/0000-0001-5715-7154	en_US
dc.contributor.author	Lin, X	en_US
dc.date.issued	2014-01-01	en_US
dc.identifier.citation	Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, pp. 827 - 838	en_US
dc.identifier.isbn	9781450323765	en_US
dc.identifier.issn	0730-8078	en_US
dc.identifier.uri	http://hdl.handle.net/10453/35406
dc.description.abstract	MapReduce has become one of the most popular parallel computing paradigms in cloud, due to its high scalability, reliability, and fault-tolerance achieved for a large variety of applications in big data processing. In the literature, there are MapReduce Class MRC and Minimal MapReduce ClassMMC to define the memory consumption, communication cost, CPU cost, and number of MapReduce rounds for an algorithm to execute in MapReduce. However, neither of them is designed for big graph processing in MapReduce, since the constraints inMMCcan be hardly achieved simultaneously on graphs and the conditions in MRC may induce scalability problems when processing big graph data. In this paper, we study scalable big graph processing in MapReduce. We introduce a Scalable Graph processing Class SGC by relaxing some constraints inMMCto make it suitable for scalable graph processing. We define two graph join operators in SGC, namely, EN join and NE join, using which a wide range of graph algorithms can be designed, including PageRank, breadth first search, graph keyword search, Connected Component (CC) computation, and Minimum Spanning Forest (MSF) computation. Remarkably, to the best of our knowledge, for the two fundamental graph problems CC and MSF computation, this is the first work that can achieve O(log(n)) MapReduce rounds with O(n + m) total communication cost in each round and constant memory consumption on each machine, where n and m are the number of nodes and edges in the graph respectively. We conducted extensive performance studies using two web-scale graphs Twitter-2010 and Friendster with different graph characteristics. The experimental results demonstrate that our algorithms can achieve high scalability in big graph processing. © 2014 ACM.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DE140100999
dc.relation.ispartof	Proceedings of the ACM SIGMOD International Conference on Management of Data	en_US
dc.relation.isbasedon	10.1145/2588555.2593661	en_US
dc.title	Scalable big graph processing in MapReduce	en_US
dc.type	Conference Proceeding
utslib.for	080101 Adaptive Agents and Intelligent Robotics	en_US
utslib.for	080109 Pattern Recognition and Data Mining	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/DVC (International)
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - ACRI - Australia China Relations Institute
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

MapReduce has become one of the most popular parallel computing paradigms in cloud, due to its high scalability, reliability, and fault-tolerance achieved for a large variety of applications in big data processing. In the literature, there are MapReduce Class MRC and Minimal MapReduce ClassMMC to define the memory consumption, communication cost, CPU cost, and number of MapReduce rounds for an algorithm to execute in MapReduce. However, neither of them is designed for big graph processing in MapReduce, since the constraints inMMCcan be hardly achieved simultaneously on graphs and the conditions in MRC may induce scalability problems when processing big graph data. In this paper, we study scalable big graph processing in MapReduce. We introduce a Scalable Graph processing Class SGC by relaxing some constraints inMMCto make it suitable for scalable graph processing. We define two graph join operators in SGC, namely, EN join and NE join, using which a wide range of graph algorithms can be designed, including PageRank, breadth first search, graph keyword search, Connected Component (CC) computation, and Minimum Spanning Forest (MSF) computation. Remarkably, to the best of our knowledge, for the two fundamental graph problems CC and MSF computation, this is the first work that can achieve O(log(n)) MapReduce rounds with O(n + m) total communication cost in each round and constant memory consumption on each machine, where n and m are the number of nodes and edges in the graph respectively. We conducted extensive performance studies using two web-scale graphs Twitter-2010 and Friendster with different graph characteristics. The experimental results demonstrate that our algorithms can achieve high scalability in big graph processing. © 2014 ACM.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/35406