Please use this identifier to cite or link to this item:
|Title:||Optimal location queries on road networks||Authors:||Tan, Zhi Heng.||Keywords:||DRNTU::Engineering
DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
|Issue Date:||2012||Abstract:||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)  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.||URI:||http://hdl.handle.net/10356/50842||Rights:||Nanyang Technological University||Fulltext Permission:||restricted||Fulltext Availability:||With Fulltext|
|Appears in Collections:||SCSE Student Reports (FYP/IA/PA/PI)|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.