text: We study algorithms for matching user tracks, consisting of time-ordered location points, to paths in the road network. Previous work has focused on the scenario where the location data is linearly ordered and consists of fairly dense and regular samples. In this work, we consider the , where the location data comes from different trips on the same route, each with very sparse samples. This captures the realistic scenario where users repeatedly travel on regular routes and samples are sparsely collected, either due to energy consumption constraints or because samples are only collected when the user actively uses a service. In the multi-track problem, the total set of combined locations is only partially ordered, rather than globally ordered as required by previous map-matching algorithms. We propose two methods, the iterative projection scheme and the graph Laplacian scheme, to solve the multi-track problem by using a single-track map-matching subroutine. We also propose a boosting technique which may be applied to either approach to improve the accuracy of the estimated paths. In addition, in order to deal with variable sampling rates in single-track map matching, we propose a method based on a particular regularized cost function that can be adapted for different sampling rates and measurement errors. We evaluate the effectiveness of our techniques for reconstructing tracks under several different configurations of sampling error and sampling rate.
  @cite_9: Vehicle tracking data is an essential "raw" material for a broad range of applications such as traffic management and control, routing, and navigation. An important issue with this data is its accuracy. The method of sampling vehicular movement using GPS is affected by two error sources and consequently produces inaccurate trajectory data. To become useful, the data has to be related to the underlying road network by means of map matching algorithms. We present three such algorithms that consider especially the trajectory nature of the data rather than simply the current position as in the typical map-matching case. An incremental algorithm is proposed that matches consecutive portions of the trajectory to the road network, effectively trading accuracy for speed of computation. In contrast, the two global algorithms compare the entire trajectory to candidate paths in the road network. The algorithms are evaluated in terms of (i) their running time and (ii) the quality of their matching result. Two novel quality measures utilizing the Frechet distance are introduced and subsequently used in an experimental evaluation to assess the quality of matching real tracking data to a road network.
  @cite_4: We extend recent results using curve simplification for approximating the Frechet distance of realistic curves in near linear time to map matching: the problem of matching a curve in an embedded graph. We show that the theoretical bounds on the running time of the previous result still hold if only one of the curves is simplified during the course of the approximation algorithm. This enables our extension to the case of map matching under the assumption that the graph is p-low density for a constant p. We present experimental evidence for this assumption and implement the extended approximate matching algorithm. We show that it performs well on real world data, such as GPS traces and road networks of urban areas. In particular, it is able to perform matching tasks that took several hours with the exact matching algorithm in under a second.
summary: Another line of research does not use any statistical methods to address the problem. Authors in @cite_4 use curve simplification for approximating the Fr 'echet distance of curves. Given a polygonal curve @math and an embedded graph @math with edges embedded as straight line segments, they attack the problem of finding the closest path in @math to the curve @math with respect to the Fr 'echet distance. @cite_9 , the average Fr 'echet distance is used to reduce the effect of outliers.