Finding a Needle in a Haystack: A Map Matching Technique for a Very Large Map Database

This paper presents a technique used in finding a certain record from a very large database. In particular, we proposed a map matching algorithm used in finding the street names which correspond to a given GPS coordinate from a large set of Bangkok map database. The GPS and map data used in this research is provided by the TRAFFY project (Traffy.in.th) from the National Electronics and Computer Technology Center in Thailand. In order to increase the speed of a map matching process, we propose the use of quad priority queues in organizing the map database. More specifically, the main focus of this paper is on how to transform the map database and use coordinate offset to expedite the search time and improve the accuracy. The proposed solution can be applied in the current traffic report system.