Name
Abstract | ||
|---|---|---|
Shortest paths and shortest path distances are important primary queries for users to query in a large graph. In this paper, we propose a new approach to answer shortest path and shortest path distance queries efficiently with an error bound. The error bound is controlled by a user-specified parameter, and the online query efficiency is achieved with prepossessing offline. In the offline preprocessing, we take a reference node embedding approach which computes the single-source shortest paths from each reference node to all the other nodes. To guarantee the user-specified error bound, we design a novel coverage-based reference node selection strategy, and show that selecting the optimal set of reference nodes is NP-hard. We propose a greedy selection algorithm which exploits the submodular property of the formulated objective function, and use a graph partitioning-based heuristic to further reduce the offline computational complexity of reference node embedding. In the online query answering, we use the precomputed distances to provide a lower bound and an upper bound of the true shortest path distance based on the triangle inequality. In addition, we propose a linear algorithm which computes the approximate shortest path between two nodes within the error bound. We perform extensive experimental evaluation on a large-scale road network and a social network and demonstrate the effectiveness and efficiency of our proposed methods. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22351-8_16 | SSDBM |
Keywords | Field | DocType |
shortest path distance,shortest path,reference node embedding,reference node,true shortest path distance,important primary query,approximate shortest path,novel coverage-based reference node,bounded error,single-source shortest path,user-specified error,large graph | Average path length,Data mining,Mathematical optimization,Shortest path problem,Computer science,Distance,Algorithm,Constrained Shortest Path First,Yen's algorithm,Shortest Path Faster Algorithm,K shortest path routing,Euclidean shortest path | Conference |
Citations | PageRank | References |
11 | 0.59 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Miao Qiao | 1 | 90 | 5.04 |
| Hong Cheng | 2 | 3694 | 148.72 |
| Jeffrey Xu Yu | 3 | 7018 | 464.96 |