We propose a new exact method for shortest-path distance queries onlarge-scale networks. Our method precomputes distance labels for vertices byperforming a breadth-first search from every vertex. Seemingly too obvious andtoo inefficient at first glance, the key ingredient introduced here is pruningduring breadth-first searches. While we can still answer the correct distancefor any pair of vertices from the labels, it surprisingly reduces the searchspace and sizes of labels. Moreover, we show that we can perform 32 or 64breadth-first searches simultaneously exploiting bitwise operations. Weexperimentally demonstrate that the combination of these two techniques isefficient and robust on various kinds of large-scale real-world networks. Inparticular, our method can handle social networks and web graphs with hundredsof millions of edges, which are two orders of magnitude larger than the limitsof previous exact methods, with comparable query time to those of previousmethods.
展开▼
