Email this article Path Planning By Caching To Avoid Shortest Path Computation
Abstract
We propose a framework, in particular, Path Planning by Caching (PPC), to answer another way arranging inquiry continuously by effectively reserving and reusing authentic questioned ways. Not at all like the regular store based way arranging frameworks, where a questioned way in reserve is utilized just when it coordinates consummately with the new inquiry, PPC use the mostly coordinated inquiries to answer part(s) of the new inquiry. Subsequently, the server just needs to register the unmatched way sections, therefore essentially diminishing the general framework workload. Complete experimentation on a genuine street organize database demonstrates that our framework outflanks the best in class way arranging methods by decreasing 32 percent of the calculation inertness by and large.
References
H. Mahmud, A. M. Amin, M. E. Ali, and T. Hashem, “Shared Execution of Path Queries on Road Networks,” Clinical Orthopaedicsand Related Research, vol. abs/1210.6746, 2012.
L. Zammit, M. Attard, and K. Scerri, “Bayesian Hierarchical Modelling of Traffic Flow - With Application to Malta’s Road Network,” in International IEEE Conference on Intelligent TransportationSystems, 2013, pp. 1376–1381.
S. Jung and S. Pramanik, “An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps,” IEEETransactions on Knowledge and Data Engineering, vol. 14, no. 5, pp. 1029–1046, 2002.
E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959.
U. Zwick, “Exact and approximate distances in graphs – a survey,” in Algorithms – ESA 2001, 2001, vol. 2161, pp. 33–48.
A. V. Goldberg and C. Silverstein, “Implementations of Dijkstra’s Algorithm Based on Multi-Level Buckets,” in Network Optimization,
P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactionson Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1967.
A. V. Goldberg and C. Harrelson, “Computing the Shortest Path: A Search Meets Graph Theory,” in ACM Symposium on DiscreteAlgorithms, 2005.
R. Gutman, “Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks,” in Workshop onAlgorithm Engineering and Experiments, 2004.
A. V. Goldberg, H. Kaplan, and R. F. Werneck, “Reach for A*: Efficient Point-to-Point Shortest Path Algorithms,” in Workshop onAlgorithm Engineering and Experiments, 2006, pp. 129–143.
Refbacks
- There are currently no refbacks.
Copyright © 2013, All rights reserved.| ijseat.com
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at http://creativecommons.org/licenses/by/3.0/deed.en_GB.