  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 \emph{multi-track map
matching}, 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.
