HotGraph: Efficient Asynchronous Processing for Real-World Graphs.

	HotGraph: Efficient Asynchronous Processing for Real-World Graphs.
	Zhang, Yu; Liao, Xiaofei; Jin, Hai; Gu, Lin; Tan, Guang; Zhou, Bing Bing
刊名	IEEE TRANSACTIONS ON COMPUTERS
	2017
文献子类	期刊论文
英文摘要	For large-scale graph analysis on a single PC, asynchronous processing methods are known to converge more quickly than the synchronous approach, because of more efficient propagation of vertices state. However, current asynchronous methods are still very suboptimal in propagating state across different graph partitions. This presents a bottleneck for cross-partition state update and slows down the convergence of the processing task. To tackle this problem, we propose a new method, named the HotGraph, to faster graph processing by extracting a backbone structure, called hot graph, that spans all the partitions of the original graph. With this approach, most cross-partition state propagations in traditional solutions now take place within only a few hot graph partitions, thus removing the cross-partition bottleneck. We also develop a partition scheduling algorithm to maximize the hot graph's effectiveness by keeping it in memory and assigning it the highest priority for processing as much as possible. A forward and backward sweeping execution strategy is then proposed to further accelerate the convergence. Experimental results show that HotGraph can reduce the number of vertex state updates processed by 51.5 percent, compared with state-of-the-art schemes. Applying our optimizations further reduces this number by 72.6 percent and the execution time by 80.8 percent.
URL标识	查看原文
语种	英语
内容类型	期刊论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/12547]
专题	深圳先进技术研究院_数字所
作者单位	IEEE TRANSACTIONS ON COMPUTERS
推荐引用方式 GB/T 7714	Zhang, Yu,Liao, Xiaofei,Jin, Hai,et al. HotGraph: Efficient Asynchronous Processing for Real-World Graphs.[J]. IEEE TRANSACTIONS ON COMPUTERS,2017.
APA	Zhang, Yu,Liao, Xiaofei,Jin, Hai,Gu, Lin,Tan, Guang,&Zhou, Bing Bing.(2017).HotGraph: Efficient Asynchronous Processing for Real-World Graphs..IEEE TRANSACTIONS ON COMPUTERS.
MLA	Zhang, Yu,et al."HotGraph: Efficient Asynchronous Processing for Real-World Graphs.".IEEE TRANSACTIONS ON COMPUTERS (2017).