TY - GEN
T1 - Proxies for shortest path and distance queries (Extended abstract)
AU - Ma, Shuai
AU - Feng, Kaiyu
AU - Li, Jianxin
AU - Wang, Haixun
AU - Cong, Gao
AU - Huai, Jinpeng
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/5/16
Y1 - 2017/5/16
N2 - This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. 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 show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-Time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and 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.
AB - This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. 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 show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-Time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and 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.
UR - http://www.scopus.com/inward/record.url?scp=85021237833&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2017.37
DO - 10.1109/ICDE.2017.37
M3 - Conference contribution
AN - SCOPUS:85021237833
T3 - Proceedings - International Conference on Data Engineering
SP - 61
EP - 62
BT - Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017
PB - IEEE Computer Society
T2 - 33rd IEEE International Conference on Data Engineering, ICDE 2017
Y2 - 19 April 2017 through 22 April 2017
ER -