南方科技大学知识苑(SUSTech KC): Distributed Edge Partitioning for Trillion-edge Graphs

题名	Distributed Edge Partitioning for Trillion-edge Graphs
作者	Hanai, Masatoshi 1,3; Suzumura, Toyotaro 2; Tan, Wen Jun 3; Liu, Elvis1 ; Theodoropoulos, Georgios1 ; Cai, Wentong 3
通讯作者	Theodoropoulos, Georgios
发表日期	2019-09
DOI	10.14778/3358701.3358706
发表期刊	Proceedings of the VLDB Endowment 影响因子和分区
ISSN	2150-8097
卷号	12 期号:13页码:2379-2392
摘要	We propose Distributed Neighbor Expansion (Distributed NE), a parallel and distributed graph partitioning method that can scale to trillion-edge graphs while providing high partitioning quality. Distributed NE is based on a new heuristic, called parallel expansion, where each partition is constructed in parallel by greedily expanding its edge set from a single vertex in such a way that the increase of the vertex cuts becomes local minimal. We theoretically prove that the proposed method has the upper bound in the partitioning quality. The empirical evaluation with various graphs shows that the proposed method produces higher-quality partitions than the state-of-the-art distributed graph partitioning algorithms. The performance evaluation shows that the space efficiency of the proposed method is an order-of-magnitude better than the existing algorithms, keeping its time efficiency comparable. As a result, Distributed NE can partition a trillion-edge graph using only 256 machines within 70 minutes.
相关链接	[来源记录]
收录类别	SCI ; EI
语种	英语
学校署名	第一 ; 通讯
资助项目	Shenzhen Peackock Programme[Y01276105]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Theory & Methods
WOS记录号	WOS:000497646100006
出版者	ASSOC COMPUTING MACHINERY
EI入藏号	20204109338794
EI分类号	Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4
来源库	Web of Science
引用统计	被引频次[WOS]：27
成果类型	期刊论文
条目标识符	http://sustech.caswiz.com/handle/2SGJ60CL/104667
专题	南方科技大学工学院_计算机科学与工程系
作者单位	1.Southern Univ Sci & Technol, Shenzhen, Guangdong, Peoples R China 2.IBM TJ Watson Res Ctr, New York, NY USA 3.Nanyang Technol Univ, Singapore, Singapore
第一作者单位	南方科技大学
通讯作者单位	南方科技大学
第一作者的第一单位	南方科技大学
推荐引用方式 GB/T 7714	Hanai, Masatoshi,Suzumura, Toyotaro,Tan, Wen Jun,et al. Distributed Edge Partitioning for Trillion-edge Graphs[J]. Proceedings of the VLDB Endowment,2019,12(13):2379-2392.
APA	Hanai, Masatoshi,Suzumura, Toyotaro,Tan, Wen Jun,Liu, Elvis,Theodoropoulos, Georgios,&Cai, Wentong.(2019).Distributed Edge Partitioning for Trillion-edge Graphs.Proceedings of the VLDB Endowment,12(13),2379-2392.
MLA	Hanai, Masatoshi,et al."Distributed Edge Partitioning for Trillion-edge Graphs".Proceedings of the VLDB Endowment 12.13(2019):2379-2392.