Map Matching and Uncertainty: an Algorithm and RealWorld Experiments

A common problem in moving object databases �MOD) is the reconstruction of a trajectory from a trajectory sample �i.e., a finite sequence of time-space points). A typical solu-tion to this problem is linear interpolation. A more realistic model is based on the notion of uncertainty modelled by space-time prisms, which capture the positions where the object could have been, when it moved from a to b. Often, object positions measured by location-aware devices are not on a road network. Thus, matching the user’s position to a location on the digital map is required. This problem is called map matching. In this paper we study the relation be-tween map matching and uncertainty, and propose an algo-rithm that combines weighted k-shortest paths with space-time prisms. We apply this algorithm to two real-world case studies and we show that accounting for uncertainty leads to obtaining more positive matchings. Categories and Subject Descriptors F.2 [Analysis of algorithms and problem complex