Name
Abstract | ||
|---|---|---|
Breadth-first graph search (a.k.a., BFS) is one of the typical in-memory computing models with complicated and frequent memory accesses. Existing single-server graph computing systems fail to take advantage of access pattern of BFS for performance optimization, hence suffering from a lot of extra memory latencies due to accessing no longer useful data elements of a big graph as well as wasting plenty of computing resources for processing them. In this article, we propose FastBFS, a new approach that accelerates breadth-first graph search on a single server by leverage of the access pattern during iterating over a big graph. First, FastBFS uses an edge-centric graph processing model to obtain the high bandwidth of sequential memory and/or disk access without expensive data preprocessing. Second, with a dynamic and asynchronous trimming mechanism, FastBFS can efficiently reduce the size of a big graph by eliminating useless edges in parallel with the computation. Third, FastBFS schedules I/O streams efficiently and can attain greater parallelism if an additional disk is available. We implement FastBFS by modifying the X-Stream system developed by EPFL. Our experimental results show that FastBFS can attain speedups of up to 7.9× and 10.4× in the computing speed compared with X-stream and GraphChi respectively. With an additional disk, the performance can be further improved. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.jpdc.2017.09.007 | Journal of Parallel and Distributed Computing |
Keywords | Field | DocType |
Graph computing,In-memory computing,I/O optimization,BFS | Graph,Asynchronous communication,Computer science,Breadth-first search,Parallel computing,Data pre-processing,Schedule,Trimming,Computation,Sequential access memory,Distributed computing | Journal |
Volume | ISSN | Citations |
120 | 0743-7315 | 0 |
PageRank | References | Authors |
0.34 | 25 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guangyan Zhang | 1 | 171 | 16.20 |
| Shu-han Cheng | 2 | 3 | 1.05 |
| Jiwu Shu | 3 | 709 | 72.71 |
| Qingda Hu | 4 | 22 | 3.78 |
| Weimin Zheng | 5 | 1889 | 182.48 |