Robust Exact Distance Queries on Massive Networks

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck

Abstract

We present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in a few microseconds. Unlike existing approaches, which are specialized, our algorithm works on a wide variety of inputs, including social, communication, sensor, and road networks. Both our indexing effort and query times are comparable to those of specialized systems. We achieve this by providing a unified framework based on the concept of 2-hop labels, building on and improving upon various existing methods. In particular, we introduce a scalable sampling-based approach to order vertices in a network. We also propose compression techniques that significantly reduce our space requirements, leading to the smallest index among algorithms with comparable query times.

Details

Publication typeTechReport
NumberMSR-TR-2014-12
PublisherMicrosoft Technical Report
> Publications > Robust Exact Distance Queries on Massive Networks