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.
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.
@cite_9 @cite_4
1544411027 2403500509
Two central limit theorems for sample Fr 'echet means are derived, both significant for nonparametric inference on non-Euclidean spaces. The first one, Theorem 2.2, encompasses and improves upon most earlier CLTs on Fr 'echet means and broadens the scope of the methodology beyond manifolds to diverse new non-Euclidean data including those on certain stratified spaces which are important in the study of phylogenetic trees. It does not require that the underlying distribution @math have a density, and applies to both intrinsic and extrinsic analysis. The second theorem, Theorem 3.3, focuses on intrinsic means on Riemannian manifolds of dimensions @math and breaks new ground by providing a broad CLT without any of the earlier restrictive support assumptions. It makes the statistically reasonable assumption of a somewhat smooth density of @math . The excluded case of dimension @math proves to be an enigma, although the first theorem does provide a CLT in this case as well under a support restriction. Theorem 3.3 immediately applies to spheres @math , @math , which are also of considerable importance in applications to axial spaces and to landmarks based image analysis, as these spaces are quotients of spheres under a Lie group @math of isometries of @math . A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with @math , a straight-line embedding on a grid of size @math can be computed deterministically in @math time with @math processors. If randomization is used, the complexity is improved to @math expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict.