Addressing the Need for Map-Matching Speed: Localizing Global Curve-Matching Algorithms

With vehicle tracking data becoming an important sensor data resource for a range of applications related to traffic assessment and prediction, fast and accurate map-matching algorithms become a necessary means to ultimately utilize this data. This work proposes a fast map-matching algorithm which exploits tracking data error estimates in a provably correct way and offers a quality guarantee for the computed result trajectory. A new model for the map-matching task is introduced which takes tracking error estimates into account. The proposed adaptive clipping algorithm (i) provably solves this map-matching task and (ii) utilizes the weak Frechet distance to measure similarity between curves. The algorithm uses the error estimates in the trajectory data to reduce the search space (error-aware pruning), while offering the quality guarantee of finding a curve which minimizes the weak Frechet distance to the vehicle trajectory among all possible curves in the road network. Moreover, this work introduces an output-sensitive variant of an existing weak Frechet map-matching algorithm, which is also employed in the adaptive clipping algorithm. Output-sensitiveness paired with error-aware pruning makes adaptive clipping the first map-matching algorithm that provably solves a well-defined map-matching task. An experimental evaluation establishes further that adaptive clipping is also in a practical setting a fast algorithm that at the same time produces high-quality matching results