Matching GPS traces to (possibly) incomplete map data: bridging map building and map matching

Analysis of geographic data often requires matching GPS traces to road segments. Unfortunately, map data is often incomplete, resulting in failed or incorrect matches. In this paper, we extend an HMM map-matching algorithm to handle missing blocks. We test our algorithm using map data from the Cyclopath geowiki and GPS traces from Cyclopath's mobile app. Even for conservative cutoff distances, our algorithm found a significant amount of missing data per set of GPS traces. We tested the algorithm for accuracy by removing existing blocks from our map dataset. As the cutoff distance was lowered, false negatives were decreased from 34% to 16% as false positives increased from 5% to 10%. Although the algorithm degrades with increasing amounts of missing data, our results show that our extensions have the potential to improve both map matches and map data.