Database Reference
In-Depth Information
match each GPS reading to a road segment, then considers the loca-
tion of the surrounding readings to correct the matched road segment.
The underlying assumption behind this approach is that the most direct
route is typically the correct one. The temporal analysis utilizes the
average speed along each road link. Yuan et al. [97] develop a voting-
based map-matching algorithm, called interactive voting map-matching
(IVMM), specifically for low sampling rate GPS data. Mapped points
are allowed to influence neighboring points with a weight inversely pro-
portional to their distances. The algorithm uses dynamic programming
to find the best scoring path given the observations.
Zheng et al. [101] introduce the first data-driven method for resolving
the inherent uncertainty of a trajectory collected using a very low GPS
sampling rate. The idea is to utilize a collection of historic trajectories
and find popular (partial) paths between the sporadic GPS observations.
The authors introduce two algorithms for solving the local path prob-
lem, one based on greedy-like search process and the other which first
extracts a traversal graph containing all of the relevant nodes and edges
between two observations and performs a shortest path search in the
reduced space. Complete trajectories are then constructed using a dy-
namic programming algorithm (and a decomposable scoring function).
In their experiments, the authors show that their approach significantly
outperforms previous methods for dealing with low-sampling-rate tra-
jectories.
Although GPS observations are the most popular type of data for
tracking and identifying an object's position, there are other options
as well. In fact, continuous collection of GPS can be quite expensive
(in terms of power consumption) for a mobile sensor. Therefore, Thi-
agarajan et al. [79] aim to utilize only the signal from cellular towers,
which requires much less energy to collect, to perform map-matching.
The authors pose this as a supervised learning problem. In this context
the training data is pairs of cellular tower fingerprints (tower IDs and
their respective signal strengths) and their corresponding GPS locations
(considered to be the labeled data). That is, using the cellular finger-
prints as a feature vector, and the GPS location of the user as the actual
location, they pose map-matching as a classification problem. Their ap-
proach grids the area of interest and uses a HMM to determine the grid
after observing the cell tower fingerprint. The authors introduce several
additional methods to clean and refine the signal, including integrating
information from other sensors on the cell phone (e.g. accelerometer
or compass). The experimental results show their method to be a very
accurate, energy ecient alternative to constantly using GPS.
