TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC

WS Han, S Lee, K Park, JH Lee, MS Kim… - Proceedings of the 19th …, 2013 - dl.acm.org
WS Han, S Lee, K Park, JH Lee, MS Kim, J Kim, H Yu
Proceedings of the 19th ACM SIGKDD international conference on Knowledge …, 2013dl.acm.org
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 …
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.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果