On Map-Matching Vehicle Tracking Data
Sotiris Brakatsoulas
1
Dieter Pfoser
1
Randall Salas
2
Carola Wenk
2
1
RA Computer Technology Institute
Akteou 11
GR-11851 Athens,Greece
{sbrakats, pfoser}@cti.gr
2
Department of Computer Science
University of Texas at San Antonio
San Antonio, TX 78249-0667, USA
{rsalas, carola}@cs.utsa.edu
Abstract
Vehicle tracking data is an essential “raw” ma-
terial for a broad range of applications such
as traffic management and control, r outing,
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 use-
ful, the data has to be related to the under-
lying road network by means of map match-
ing algorithms. We present three such algo-
rithms that consider especially the trajectory
nature of the data rather than simply the cur-
rent position as in the typical map-matching
case. An incremental algorithm is proposed
that matches consecutive portions of the tra-
jectory to the road network, effectively trad-
ing 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 Fr´echet distance
are introduced and subsequently used in an
experimental evaluation to assess the quality
of matching real tracking data to a road net-
work.
1 Introduction
As roads become more and more congested, much re-
search is conducted in the area of traffic estimation and
Permission to copy without fee all or part of this material is
granted provided that the copies are not made or distributed for
direct commercial advantage, the VLDB copyright notice and
the title of the publication and its date appear, and notice is
given that copying is by permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires a fee
and/or special permission from the Endowment.
Proceedings of the 31st VLDB Conference,
Trondheim, Norway, 2005
prediction systems (TREPS). TREPS use traffic mod-
els together with sensor data to assess the current and
to predict the future traffic conditions in the road net-
work. Currently, the data component consists of traf-
fic counts (quantitative data) obtained by stationary
sensors, typically loop detectors, which are deployed
throughout the road network. In recent years, a new
sensor technology is utilized to complement station-
ary sensor networks. Floating car data (FCD) refers
to using data generated by one vehicle as a sample to
assess the over all traffic conditions (“cork swimming
in the river”). Typically this data comprises basic ve-
hicle telemetry such as speed direction and most im-
portantly the position of the vehicle. Recording the
position of vehicles in time produces tracking data, of
which, in connection with a road network, travel time
data (qualitative data) is derived. Having large num-
bers of vehicles collecting such data for a given spatial
area such as a city (e.g., taxis, public transport, utility
vehicles, private vehicles, etc.) will create an accurate
picture of the traffic condition in time and space [10].
Data management techniques for such FCD collections
are presented in [6].
The tracking data is obtained by sampling the po-
sitions using typically GPS to produce data that in
database terms is commonly referred to as trajecto-
ries. Unfortunately, this data is not precise due to the
measurement error caused by the limited GPS accu-
racy, and the sampling error caused by the sampling
rate [14]. A pre-processing step that matches the tra-
jectories to the road network is needed. This technique
is commonly referred to as map matching.
Most map-matching algorithms are tailored towards
mapping current positions onto a vector representa-
tion of a road network. Onboard systems for vehicle
navigation utilize besides continuous positioning also
dead reckoning to minimize the positioning error and
to produce accurate vehicle positions that can be easily
matched to a road map. In the given context, the en-
tire trajectory given as a sequence of historic position
samples needs to be mapped. The fundamental dif-
ference in these two approaches is the error associated
with the data. W hereas the data in the former case is
853
