Towards online shortest path problem aims at
computing the shortest path based on live traffic
circumstances and recommends the best path. This is very
important in modern car navigation systems as it helps
drivers to make sensible decisions. To our best knowledge,
there is no efficient system/solution that can offer affordable
costs at both client and server sides for online shortest path
computation. Unfortunately, the conventional client-server
architecture scales poorly with the number of clients. A
promising approach is to let the server collect live traffic
information and then broadcast them over radio or wireless
network. This approach has excellent scalability with the
number of clients. Thus, it develop a new framework called
live traffic index (LTI) which enables drivers to quickly and
effectively collect the live traffic information on the
broadcasting channel. An impressive result is that the driver
can compute/update their shortest path result by receiving
only a small fraction of the index. Our experimental study
shows that LTI is robust to various parameters and it offers
relatively short tune-in cost (at client side), fast query
response time (at client side), small broadcast size (at server
side), and light maintenance time (at server side) for online
shortest path problem.
In this paper studies online shortest path computation; the
shortest path result is computed/updated based on the live
traffic circumstances. It carefully analyze the existing
work and discuss their inapplicability to the problem. To
address the problem, it suggest a promising architecture
that broadcasts the index on the air. This first identify an
important feature of the hierarchical index structure which
enables us to compute shortest path on a small portion of
index. This important feature is thoroughly used in our
solution, LTI.
[1] “Navteq maps and traffic,”
http://www.navteq.com,2014
[2] “TomTom NV,” http://www.tomtom.com, 2014.
[3] ”Google Maps,” http://maps.google.com, 2014.
[4] “Cisco Visual Networking Index: Global Mobile Data
Traffic Forecast Update, 2010-2015,” 2011.
[5] N.Malviya,S.Madden, and A. Bhattacharya, “A
Continuous Query System for Dynamic Route
Planning,” Proc. IEEE 27th Int’lConf Data Eng.
(ICDE), pp. 792-803, 2011.
[6] G. Kellaris and K. Mouratidis, “Shortest Path
Computation on Air Indexes,” Proc. VLDB
Endowment, vol. 3, no. 1, pp. 741-757, 2010.
[7] J.X. Yu and K.-L. Tan, “An Analysis of Selective
Tuning Schemes for Nonuniform Broadcast,”
Data and Knowledge Eng., vol. 22, no. 3, pp.
319-344, 1997.
[8] G.Dantzig, Linear Programming and Extensions, series
Rand Corporation Research Study Princeton
Univ.Press, 1963.
[9] A.V. Goldberg and R.F.F. Werneck, “Computing
Point-to-Point Shortest Paths from External
Memory,”Proc. SIAM Workshop Algorithms Eng. and
Experimentation and the Workshop Analytic
Algorithmics and
Combinatorics(ALENEX/ANALCO), pp. 26-40, 2005.
[10] M. Hilger, E. K€ohler, R. M€ohring, and H.
Schilling,“Fast Point-to- Point Shortest Path
Computations with Arc-Flags,” The Shortest Path
Problem: Ninth DIMACS Implementation Challenge,
vol. 74,pp. 41- 72, American Math. Soc., 2009.
[11] D. Delling and D. Wagner, “Landmark-Based Routing
in Dynamic Graphs,” Proc. Sixth Int’l Workshop
Experimental Algorithms (WEA),pp. 52-65,
2007. [12] R.J. Gutman, “Reach-Based Routing: A
New Approach to Shortest Path Algorithms
Optimized for Road Networks,” Proc. Sixth Workshop
Algorithm Eng. and Experiments and the First
Workshop Analytic Algorithmics and
Combinatorics (ALENEX/ANALC),pp.100-111,
2004.
[13] B. Jiang, “I/O-Efficiency of Shortest Path
Algorithms:An Analysis,”Proc. Shortest Path
Queries,” Proc. 13th Ann.European Conf.
[14] P. Sanders and D. Schultes, “Highway Hierarchies
Hasten Exact Shortest Path Queries,” Proc. 13th
Ann.European Conf. Algorithms(ESA), pp. 568-
579, 2005.
[15] R. Geisberger, P. Sanders, D. Schultes, and D. Delling,
“Contraction Hierarchies: Faster and Simpler
Hierarchical Routing in Road Networks,” Proc.
Seventh Int’l Workshop Experimental Algorithms
(WEA),pp. 319-333,2008.
[16] S. Jung and S. Pramanik, “An Efficient Path
Computation Model for Hierarchically
Structured Topographical Road Maps,” IEEE Trans.
Knowledge and Data Eng., vol. 14, no. 5, pp. 1029-
1046, Sept. 2002.
[17] E.P.F. Chan and Y. Yang, “Shortest Path Tree
Computation in Dynamic Graphs,” IEEE Trans.
Computers, vol. 58, no. 4, pp. 541-557, Apr.
2009.
[18] T. Beuhler and M. Hein, “Spectral Clustering Based on
The Graph – Laplacian,” Proc. Int’l Conf.
Machine Learning (ICML), p. 11, 2009.
[19] T. Imielinski, S. Viswanathan, and B.R.Badrinath,
“Data on Air:Organization and Access,” IEEE Trans.Knowledge and Data Eng.,vol. 9, no. 3,
pp. 353-372.
[20] IEEE Transactions on Knowledge and Data
Engineering, Vol. 26, No. 4, April 2014,”Towards
Online Shortest Path Computation” Leong Hou U,
Hong Jun Zhao, Man Lung Yiu, Yuhong Li, and
Zhiguo Gong.
