Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/50842
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) [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.
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)

Files in This Item:
File Description SizeFormat 
SCE11-0512.pdf
  Restricted Access
Main article866.73 kBAdobe PDFView/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.