FastBFS: Fast Breadth-First Graph Search on a Single Server

摘要

Big graph computing can be performed over a single node, using recent systems such as GraphChi and XStream. Breadth-first graph search (a.k.a., BFS) has a pattern of marking each vertex only once as “visited” and then not using them in further computations. Existing single-server graph computing systems fail to take advantage of such access pattern of BFS for performance optimization, hence suffering from a lot of extra I/O 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 paper, we propose FastBFS, a new approach that accelerates breadth-first graph search on a single server by leverage of the preceding access pattern during the BFS iterations over a big graph. First, FastBFS uses an edgecentric graph processing model to obtain the high bandwidth of sequential disk accesses without expensive data preprocessing. Second, with a new 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 outperform X-stream and GraphChi in the computing speed by up to 2.1 and 3.9 times faster respectively. With an additional disk, FastBFS can even outperform them by up to 3.6 and 6.5 times faster respectively.