Proxies for Shortest Path and Distance Queries

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 routi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2016-07, Vol.28 (7), p.1835-1850
Main Authors: Ma, Shuai, Feng, Kaiyu, Li, Jianxin, Wang, Haixun, Cong, Gao, Huai, Jinpeng
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Data preprocessing
Data reduction
Design engineering
Gold
Graphs
Indexes
Mathematical models
Queries
Roads
Routing
shortest distances
Shortest paths
Shortest-path problems
Social network services
speeding-up techniques
Tasks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2016.2531667