Proxies for Shortest Path and Distance Queries
Shuai Ma, Kaiyu Feng, Jianxin Li, Haixun Wang, Gao Cong, Jinpeng Huai · IEEE Transactions on Knowledge and Data Engineering · 2016
Computing shortest paths and distances is one of the fundamental problems on graphs, and it remains a challenging task today. This article investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. To do this, we propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We first show that routing proxies hold good properties for speeding-up shortest path and distance queries. Then, we design a linear-time algorithm to compute routing proxies and their corresponding DRAs. Finally, we experimentally verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.