Towards Efficient Shortest Path Counting on Billion-Scale Graphs

Shortest path counting computes the number of shortest paths between two vertices on a graph, which can be used in the applications such as social network search and POI (Point of Interest) recommendation. The state-of-the-art approach leverages index to speed up the query processing. However, this approach incurs not only significant space overheads but also prohibitive indexing time, which makes it inapplicable to handle such queries on large graphs. Motivated by this, in this paper, we aim to propose a new solution to scale up the shortest path counting. To achieve this goal, we first propose a novel size-tunable indexing framework, which allows users to tune the index space consumption based on their requirements for query processing efficiency and available memory. Based on the size-tunable indexing framework, we devise a new parallel paradigm to accelerate index construction. We conduct experiments on 15 real graphs and the experimental results demonstrate that our new approach significantly outperforms the state-of-the-art approach regarding the index space cost and index construction cost, and is able to handle billion-scale graphs that the state-of-the-art approach cannot process with less than 5 milliseconds query processing time on all test cases.