Matching GPS Records to Digital Map Data: Algorithm Overview and Application

Records of latitude and longitude pairs describing an approximate path of travel are logged by many types of Global Positioning System (GPS)-enabled devices. These logs of latitude/longitude (lat/lon) pairs specify geographic locations but include error inherent in the GPS system. Digital map data include representations of roads, trails, airways, etc., with links and nodes that are located geospatially but that also include error. The following report describes an algorithm for matching GPS points to the correct road link in digital map data by using road network connectivity. The algorithm was applied to the naturalistic driving data from the second Strategic Highway Research Program (SHRP 2), the largest naturalistic driving study to date. The data set from SHRP 2 consists of 5.5 million trips, which generated approximately 3.7 billion latitude/longitude pairs that needed to be matched to roads represented in digital maps. When identifying roads from GPS data at this scale, both the processing speed and the accuracy of the algorithm are important. To evaluate the output accuracy, a sample of 100 randomly selected trips was compared to a manual route identification. The results indicate that the algorithm assigned driving data to the correct link 91% of the time. When the driving data were not on a link, the algorithm correctly recognized this 86% of the time.