Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
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 real time. Unlike existing approaches, preprocessing and queries are practical on a wide variety of inputs, such as social, communication, sensor, and road networks. We achieve this by providing a unified approach based on the concept of 2-hop labels, improving upon existing methods. In particular, we introduce a fast sampling-based algorithm to order vertices by importance, as well as effective compression techniques.

We updated the TR in July 2014.

Details

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