Optimal location queries on road networks

• Main Author: Tan, Zhi Heng.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering; DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
• Online Access: http://hdl.handle.net/10356/50842
• Institution: Nanyang Technological University

Graph size of dataset used in programs is getting larger and the details on it are getting refined over times, therefore the need for a more sophisticated Graph Traversal Algorithm arises. The new algorithm must be fast and also scalable to handle the searching between any two points in a map. This report is about the use of the Contraction hierarchies with label restrictions (CHLR) [1] to hasten the process of finding the shortest path between any two points in a road network. It hastens the searching process by introducing shortcuts between points. By using a bidirectional Dijkstra search variant, along with some absolute ordering of the nodes, we are able to omit expanding the search, only to some nodes while maintaining the accuracy of the search. We will also introduce multithreading and storing of data into separate files to help reduce computation time while carrying out the indexing of the graph. Performance testing is carried out to determine how well threads perform in sequential and parallel mode. From the results shown there was significant reduction in indexing time, and achieved a speed up of 1.423.