2013 TurboGraphAFastParallelGraphEng

• (Han et al., 2013) ⇒ Wook-Shin Han, Sangyeon Lee, Kyungyeol Park, Jeong-Hoon Lee, Min-Soo Kim, Jinha Kim, and Hwanjo Yu. (2013). “TurboGraph: A Fast Parallel Graph Engine Handling Billion-scale Graphs in a Single PC.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487581

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+TurboGraph%3A+A+Fast+Parallel+Graph+Engine+Handling+Billion-scale+Graphs+in+a+Single+PC
• http://dl.acm.org/citation.cfm?id=2487575.2487581&preflayout=flat#citedby

Quotes

Author Keywords

Big data; graph processing; parallel databases; parallelism; pin-and-slide; [[search process

Abstract

Graphs are used to model many real objects such as social networks and web graphs. Many real applications in various fields require efficient and effective management of large-scale graph structured data. Although distributed graph engines such as GBase and Pregel handle billion-scale graphs, the user needs to be skilled at managing and tuning a distributed system in a cluster, which is a nontrivial job for the ordinary user. Furthermore, these distributed systems need many machines in a cluster in order to provide reasonable performance. In order to address this problem, a disk-based parallel graph engine called Graph-Chi, has been recently proposed. Although Graph-Chi significantly outperforms all representative (disk-based) distributed graph engines, we observe that Graph-Chi still has serious performance problems for many important types of graph queries due to 1) limited parallelism and 2) separate steps for I/O processing and CPU processing. In this paper, we propose a general, disk-based graph engine called TurboGraph to process billion-scale graphs very efficiently by using modern hardware on a single PC. TurboGraph is the first truly parallel graph engine that exploits 1) full parallelism including multi-core parallelism and FlashSSD IO parallelism and 2) full overlap of CPU processing and I/O processing as much as possible. Specifically, we propose a novel parallel execution model, called pin-and-slide. TurboGraph also provides engine-level operators such as BFS which are implemented under the pin-and-slide model. Extensive experimental results with large real datasets show that TurboGraph consistently and significantly outperforms Graph-Chi by up to four orders of magnitude ! Our implementation of TurboGraph is available at “http://wshan.net / turbograph} " as executable files.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 TurboGraphAFastParallelGraphEng	Hwanjo Yu Wook-Shin Han Sangyeon Lee Kyungyeol Park Jeong-Hoon Lee Min-Soo Kim Jinha Kim			TurboGraph: A Fast Parallel Graph Engine Handling Billion-scale Graphs in a Single PC				10.1145/2487575.2487581		2013