Yufei Tao
ABSTRACT
Given two vertices s, t in a graph, let P be the shortest path (SP) from s to t, and P* a subset of the vertices in P. P* is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P. In general, P* succinctly describes P by sampling the vertices in P with a rate of at least 1/k. This makes P* a natural substitute in scenarios where reporting every single vertex of P is unnecessary or even undesired.
This paper studies k-skip SP computation in the context of spatial network databases (SNDB). Our technique has two properties crucial for real-time query processing in SNDB. First, our solution is able to answer k-skip queries significantly faster than finding the original SPs in their entirety. Second, the previous objective is achieved with a structure that occupies less space than storing the underlying road network. The proposed algorithms are the outcome of a careful theoretical analysis that reveals valuable insight into the characteristics of the k-skip SP problem. Their efficiency has been confirmed by extensive experiments with real data.
- I. Abraham, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 782--793, 2010. Google Scholar
Digital Library
- R. Agrawal and H. V. Jagadish. Algorithms for searching massive graphs. IEEE Transactions on Knowledge and Data Engineering (TKDE), 6(2):225--238, 1994. Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001. Google ScholarDigital Library
- K. Deng, X. Zhou, H. T. Shen, S. W. Sadiq, and X. Li. Instance optimal query processing in spatial networks. The VLDB Journal, 18(3):675--693, 2009. Google ScholarDigital Library
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.Google ScholarDigital Library
- R. Durstenfeld. Algorithm 235: Random permutation. Communications of the ACM (CACM), 7(7):420, 1964. Google ScholarDigital Library
- G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal of Computing, 16(6):1004--1022, 1987. Google ScholarDigital Library
- R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of Workshop on Experimental Algorithms (WEA), pages 319--333, 2008. Google ScholarDigital Library
- A. V. Goldberg and C. Harrelson. Computing the shortest path: $A^*$ search meets graph theory. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 156--165, 2005. Google ScholarDigital Library
- A. V. Goldberg, H. Kaplan, and R. F. Werneck. Reach for A*: Shortest path algorithms with preprocessing. In Proceedings of Workshop on Algorithm Engineering and Experiments (ALENEX), pages 38--51, 2006.Google Scholar
- A. Gubichev, S. J. Bedathur, S. Seufert, and G. Weikum. Fast and accurate estimation of shortest paths in large graphs. In Proceedings of Conference on Information and Knowledge Management (CIKM), pages 499--508, 2010. Google ScholarDigital Library
- R. J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of Workshop on Algorithm Engineering and Experiments (ALENEX), pages 100--111, 2004.Google Scholar
- P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Science and Cybernetics, 4(2):100--107, 1968.Google ScholarCross Ref
- D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127--151, 1987.Google ScholarDigital Library
- D. A. Hutchinson, A. Maheshwari, and N. Zeh. An external memory data structure for shortest path queries. Discrete Applied Mathematics, 126(1):55--82, 2003. Google ScholarDigital Library
- N. Jing, Y.-W. Huang, and E. A. Rundensteiner. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. IEEE Transactions on Knowledge and Data Engineering (TKDE), 10(3):409--432, 1998. Google ScholarDigital Library
- S. Jung and S. Pramanik. An efficient path computation model for hierarchically structured topographical road maps. IEEE Transactions on Knowledge and Data Engineering (TKDE), 14(5):1029--1046, 2002. Google ScholarDigital Library
- M. R. Kolahdouzan and C. Shahabi. Alternative solutions for continuous k nearest neighbor queries in spatial network databases. GeoInformatica, 9(4):321--341, 2005. Google ScholarDigital Library
- U. Lauther. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. Geoinformation und Mobilitat - von der Forschung zur praktischen Anwendung, 22:219--230, 2004.Google Scholar
- T. A. J. Nicholson. Finding the shortest route between two points in a network. The Computer Journal, 9:275--280, 1966.Google ScholarCross Ref
- M. Potamias, F. Bonchi, C. Castillo, and A. Gionis. Fast shortest path distance estimation in large networks. In Proceedings of Conference on Information and Knowledge Management (CIKM), pages 867--876, 2009. Google ScholarDigital Library
- M. N. Rice and V. J. Tsotras. Graph indexing of road networks for shortest path queries with label restrictions. Proceedings of the VLDB Endowment (PVLDB), 4(2):69--80, 2010. Google ScholarDigital Library
- N. Robertson and P. D. Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49--64, 1984.Google ScholarCross Ref
- H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In Proceedings of ACM Management of Data (SIGMOD), pages 43--54, 2008. Google ScholarDigital Library
- P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In Proceedings of European Symposium on Algorithms (ESA), pages 568--579, 2005. Google ScholarDigital Library
- P. Sanders and D. Schultes. Engineering highway hierarchies. In Proceedings of European Symposium on Algorithms (ESA), pages 804--816, 2006. Google ScholarDigital Library
- J. Sankaranarayanan, H. Samet, and H. Alborzi. Path oracles for spatial networks. Proceedings of the VLDB Endowment (PVLDB), 2(1):1210--1221, 2009. Google ScholarDigital Library
- D. Wagner, T. Willhalm, and C. D. Zaroliagis. Geometric containers for efficient shortest-path computation. ACM Journal of Experimental Algorithmics, 10, 2005. Google ScholarDigital Library
- F. Wei. Tedi: Efficient shortest path query answering on graphs. In Proceedings of ACM Management of Data (SIGMOD), pages 99--110, 2010. Google ScholarDigital Library
- Y. Xiao, W. Wu, J. Pei, W. Wang, and Z. He. Efficiently indexing shortest paths by exploiting symmetry in graphs. In Proceedings of Extending Database Technology (EDBT), pages 493--504, 2009. Google ScholarDigital Library
Index Terms
- On k-skip shortest paths
Recommendations
On shortest disjoint paths in planar graphs
For a graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}, the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the ...
Shortest paths in Sierpiński graphs
In 23], Klav ar and Milutinović (1997) proved that there exist at most two different shortest paths between any two vertices in Sierpiński graphs S k n , and showed that the number of shortest paths between any fixed pair of vertices of S k n can be ...
Shortest vertex-disjoint two-face paths in planar graphs
Let G be a directed planar graph of complexity n, each arc having a nonnegative length. Let s and t be two distinct faces of G let s1,…,sk be vertices incident with s let t1,…,tk be vertices incident with t. We give an algorithm to compute k pairwise ...
Comments