Online shortest path computation using Live Traffic index

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
© 2015 by IJETT Journal
Volume-25 Number-3
Year of Publication : 2015
Authors : Dekonda Sindhuja, R Vasavi, A Kousar Nikhath
DOI :  10.14445/22315381/IJETT-V25P227


Dekonda Sindhuja, R Vasavi, A Kousar Nikhath "Online shortest path computation using Live Traffic index", International Journal of Engineering Trends and Technology (IJETT), V25(3),145-149 July 2015. ISSN:2231-5381. published by seventh sense research group

Online Shortest path computation using live traffic index in road networks aims at computing the shortest path from source to destination using Live traffic index. In this paper index transmission model along with Live traffic index technique is used. In this technique, first the traffic provider collects the traffic data and transmits to the traffic server broadcaster. The traffic server broadcaster indexes and optimizes the traffic data and broadcasts to the navigation client. Graph partitioning and stochastic process are the new techniques used to optimize the index. The fast query response time and short tune in cost at client side ,small broadcast size and maintenance time at server side are the extra features achieved in the system.


[1] ? NAVTEQ Maps and Traffic,?, 2014
[2] ?TomTom NV,, 2014.
[3] Google Maps,, 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. B€uhler 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.

Live traffic index, Stochastic process, Shortest path.