The Design And Implementation Of Fast Out-of-core Graph Processing Framework

It is rational to use graphs with data associated with its vertices and edges(ie., data-graphs) to model real world problems. With the advent of big data era, the size of today’s real-world graphs continuously increases, which places huge challenge for the processing systems of graph data mining. This challenge has fostered the building of graph processing systems. Some system that process the graph data on single PCs are rather interesting and of practical uses, because one has easy access on a single PC. However, there may be no enough main memory on to load the whole graph on a single PC, which means that the systems have to utilize the disks, to store the data-graph as well as the intermediate computing results. Existing similar systems excessively emphasize sequential accesses to the disks in order to achieve high data-access efficiency. However, it results in huge waste in the loaded data.A fast out-of-core graph processing framework on single PCs(FOG) addresses such limitations by realizing a fast indexing mechanism by leveraging the virtual memory management system of operating system, which combines a hybrid scheduling strategy based on bitmap to acquire only the demanded data to reduce the wastes. Moreover, by processing the graph by edges, FOG processes an in-place shuffling mechanism as well as a methodology that converts small and random update into sequential disk accesses such that greatly reduces the overhead during update handling.By conducting representative algorithms on real-world graphs stored in both Solid State Drives(SSDs) and Hard Disk Drives(HDDs), experiment results show that FOG achieved fast execution speed. Compared with Graph Chi and X-Stream, the performance improvement of a graph algorithm by FOG can be up to 25x+. Compared with Turbo Graph, the performance improvement of a graph algorithm by FOG can be up to 3.8x.