Inference of shortest path algorithms with spatial and temporal locality for Big Data processing

Abstract

The all-pair shortest paths problemon large-size graphs has many crucial application domains in science, engineering and economics. Such computer architectures as multi-core systems explore hierarchical memory consisting of local and shared levels, which differ on memory capacity and data transfer time delays. The cores read and write data through the fast local caches, therefore running algorithms which support locality in big data processing are most efficient. The paper develops an inference technique at the aim of creating all-pair shortest paths algorithms that improve the spatial and temporal reference locality and reduce the cache pressure. It proposes and transforms a graph-extension-based shortest paths search algorithm that obtains the reference locality properties and recalculates the lengths of shortest paths at each step of adding a vertex to the graph. Every step of algorithm transformation introduces additional temporal or spatial locality. Computational experiments carried out on two types of multi-core processor and on graphs of thousands of vertices have shown about 40% speedup of the proposed algorithm against the classic Floyd-Warshall one. The proposed algorithm has also shown a gain of 25 – 35% over the blocked Floyd-Warshall algorithm, which has the property of spatial data locality.