Robust Exact Distance Queries on Massive Networks

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.

RXL.pdf
PDF file

Publisher  Microsoft Technical Report

Details

TypeTechReport
NumberMSR-TR-2014-12
> Publications > Robust Exact Distance Queries on Massive Networks