  Processing very large graphs like social networks, biological and chemical
compounds is a challenging task. Distributed graph processing systems process
the billion-scale graphs efficiently but incur overheads of efficient
partitioning and distribution of the graph over a cluster of nodes. Distributed
processing also requires cluster management and fault tolerance. In order to
overcome these problems GraphChi was proposed recently. GraphChi significantly
outperformed all the representative distributed processing frameworks. Still,
we observe that GraphChi incurs some serious degradation in performance due to
1) high number of non-sequential I/Os for processing every chunk of graph; and
2) lack of true parallelism to process the graph. In this paper we propose a
simple yet powerful engine BiShard Parallel Processor (BPP) to efficiently
process billions-scale graphs on a single PC. We extend the storage structure
proposed by GraphChi and introduce a new processing model called BiShard
Parallel (BP). BP enables full CPU parallelism for processing the graph and
significantly reduces the number of non-sequential I/Os required to process
every chunk of the graph. Our experiments on real large graphs show that our
solution significantly outperforms GraphChi.

Data Structures and Algorithms;Databases