Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement

Download PDF

Abstract

Shortest-path queries, as a basic operation in complex networks, have plentiful applications. One option for answering shortest-path queries is to use online traversal, such as breadth-first search, but this results in excessively long query time. Another option is to extend the existing index-based methods for handling shortest-distance queries to support shortest-path queries. However, the extra space required by the extension causes the total index size to be too large. To achieve an elegant trade-off between query time and index size, we propose a new index-based approach, Monotonic Landmark Labeling (MLL), to process shortest-path queries. MLL works by decomposing the shortest path between two vertices into several subpaths, which are then indexed. At query time, the shortest path can be found efficiently by finding and splicing the subpaths. We verify that the MLL index is small, and we propose a parallel algorithm for creating it efficiently. Extensive experiments show that the MLL index size is bounded by 23 GB on all tested graphs, and the queries can be answered within 2 milliseconds, even on billion-scale graphs.