An Active Cache-Supported Path Planning on Roads

Article Sidebar

PDF
Published: Nov 28, 2017
Keywords:
Path Planning by Caching (PPC), GPS, Cache Management, PPattern Detection

Main Article Content

Chimme.Mahendranath
V.Leena Parimala

Abstract

In mobile navigation positions, on-road path planning is an essential dimension that finds a sequence between a source area and the destination point. While on streets, the away organizing question might be scattered because of portion considers different circumstances, for the case, a sudden change in driving path, startling activity conditions, or loss of GPS signals. In these situations, path planning needs to be directed promptly. The requirement of timeliness is even more confusing when a vast number of path planning queries acquiesces to the server, e.g., during peak hours. As the response time is unjustified to user approval with personal navigation services, it is a mandate for the server to handle the massive workload of path planning requests efficiently. To handle issues with the presented system, we recommend a scheme, namely, Path Planning by Caching (PPC), that objectives to response a different path planning query efficiently by caching and reprocessing queried paths (queried-paths in short). Distinct conventional cache-based path planning systems where a cached query degenerates just once it matches entirely with an original query, PPC leverages partially matched queried-paths in the cache to response part(s) of the different query. As a consequence, the server only needs to figure the unmatched path segments, thus significantly reducing the overall system workload.

Article Details

How to Cite
[1]
Chimme.Mahendranath and V.Leena Parimala, “An Active Cache-Supported Path Planning on Roads”, Int. J. Comput. Eng. Res. Trends, vol. 4, no. 11, pp. 461–468, Nov. 2017.
Issue
Vol. 4 No. 11 (2017): November (2017) Issue
Section
Research Articles
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

IJCERT Policy:

The published work presented in this paper is licensed under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. This means that the content of this paper can be shared, copied, and redistributed in any medium or format, as long as the original author is properly attributed. Additionally, any derivative works based on this paper must also be licensed under the same terms. This licensing agreement allows for broad dissemination and use of the work while maintaining the author's rights and recognition.

By submitting this paper to IJCERT, the author(s) agree to these licensing terms and confirm that the work is original and does not infringe on any third-party copyright or intellectual property rights.

 

References

N. Mondal, M. Bag, M. Mukherjee, S. Chatterjee, N. Pervin, G. C. Banerjee,†Characteristics and Nature of Routing Protocols Used in VANET: A Comprehensive Study. “International Journal of Computer Engineering in Research Trends., vol.2, no.5, pp.284-287, 2015.

Ramesh S Gawali, Prof. Mrunali G. Vaidya,†Selection and Maintenance of Materialized Views using Genetic Algorithm. “International Journal of Computer Engineering in Research Trends., vol.3, no.12, pp. 629-631, 2016.

M.SHIRISHA, M.RADHA,†AMES-Cloud: A Framework of AMOV & ESOL using Clouds. “International Journal of Computer Engineering in Research Trends., vol.2, no.5, pp. 305-309, 2015.

Shital M Kuwarkar, Prof. U.A.Nul,†Energy Consumption on Smartphone Web Browsing in 3G Network. “International Journal of Computer Engineering in Research Trends., vol.4, no.7, pp. 290-295, 2017.

Dr. Subhi R. M. Zeebaree, Karwan Jacksi,†Effects of Processes Forcing on CPU and Total Execution-Time Using Multiprocessor Shared Memory Systemd. “International Journal of Computer Engineering in Research Trends., vol.2, no.4, pp. 275-279, 2015.

Mr .BETKAR AKSHAY SURESH, Mrs. N.SUJATHA,†PROGRESSIVE DUPLICATE DETECTION. “International Journal of Computer Engineering in Research Trends., vol.3, no.6, pp. 284-288, 2016.

H. Mahmud, A. M. Amin, M. E. Ali, and T. Hashem, “Shared Execution of Path Queries on Road Networks,†Clinical Orthopaedics and 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 Transportation Systems, 2013, pp. 1376–1381.

S. Jung and S. Pramanik, “An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps,†IEEE Transactions 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 Transactions on 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 Discrete Algorithms, 2005.

R. Gutman, “Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks,†in Workshop on Algorithm 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 on Algorithm Engineering and Experiments, 2006, pp. 129–143.

S. Jung and S. Pramanik, “An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps,†IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 5, pp. 1029–1046, 2002.

R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina, “Proximity Search in Databases,†in International Conference on Very Large Data Bases, 1998, pp. 26–37.

N. Jing, Y.-W. Huang, and E. A. Rundensteiner, “Hierarchical Optimization of Optimal Path Finding for Transportation Applications,†in ACM Conference on Information and Knowledge Management, 1996.

N. Jing, Y. wu 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, vol. 10, pp. 409–432, 1998.

U. Demiryurek, F. Banaei-Kashani, C. Shahabi, and A. Ranganathan, “Online Computation of Fastest Path in Time-Dependent Spatial Networks,†in International Conference on Advances in Spatial and Temporal Databases, 2011.

H. Gonzalez, J. Han, X. Li, M. Myslinski, and J. P. Sondag, “Adaptive Fastest Path Computation on a Road Network: a Traffic Mining Approach,†in International Conference on Very Large Data Bases, 2007.

J. R. Thomsen, M. L. Yiu, and C. S. Jensen, “Effective caching of shortest paths for location-based services,†in ACM International Conference on Management of Data, 2012.