Map-Matching for Low-Sampling-Rate GPS Trajectories
Yin Lou
Microsoft Research Asia
v-yilou@microsoft.com
Xing Xie
Microsoft Research Asia
xingx@microsoft.com
Chengyang Zhang
Microsoft Research Asia
v-chenz@microsoft.com
Wei Wang
Fudan University
weiwang1@fudan.edu.cn
Yu Zheng
Microsoft Research Asia
yuzheng@microsoft.com
Yan Huang
University of North Texas
huangyan@unt.edu
ABSTRACT
Map-matching is the process of aligning a sequence of observed
user positions with the road network on a digital map. It is a
fundamental pre-processing step for many applications, such as
moving object management, traffic flow analysis, and driving
directions. In practice there exists huge amount of low-sampling-
rate (e.g., one point every 2-5 minutes) GPS trajectories.
Unfortunately, most current map-matching approaches only deal
with high-sampling-rate (typically one point every 10-30s) GPS
data, and become less effective for low-sampling-rate points as
the uncertainty in data increases. In this paper, we propose a novel
global map-matching algorithm called ST-Matching for low-
sampling-rate GPS trajectories. ST-Matching considers (1) the
spatial geometric and topological structures of the road network
and (2) the temporal/speed constraints of the trajectories. Based
on spatio-temporal analysis, a candidate graph is constructed
from which the best matching path sequence is identified. We
compare ST-Matching with the incremental algorithm and
Average-Fréchet-Distance (AFD) based global map-matching
algorithm. The experiments are performed both on synthetic and
real dataset. The results show that our ST-matching algorithm
significantly outperform incremental algorithm in terms of
matching accuracy for low-sampling trajectories. Meanwhile,
when compared with AFD-based global algorithm, ST-Matching
also improves accuracy as well as running time.
Categories and Subject Descriptors
H.2.8 [Database Applications]: Spatial Databases and GIS.
General Terms
Algorithms, Design
Keywords
Map-matching, GPS, trajectory, road network
1. INTRODUCTION
The past years have seen a dramatic increase of handheld or
dashboard-mounted travel guidance systems and GPS-embedded
PDAs and smart phones. The proliferation of these devices has
enabled the collection of huge amount of GPS trajectories. More
and more applications, such as route planner [7], hot route finder
[16], traffic flow analysis [15], geographical social network [23],
have started to use information from GPS data to achieve better
quality of services.
Typically a GPS trajectory consists of a sequence of points with
latitude, longitude, and timestamp information. However, this data
is not precise due to measurement errors caused by the limitation
of GPS devices and sampling error caused by the sampling rate
[17]. Therefore the observed GPS positions often need to be
aligned with the road network on a given digital map. This
process is called map-matching. Map-matching is a fundamental
pre-processing step for many trajectory-based applications, such
as moving object management, traffic flow analysis, and driving
directions. The difficulty of map-matching can greatly differ
depending on GPS accuracy and the sampling rate.
This paper addresses the problem of sampling error in particular.
In practice there exists large amount of low-sampling-rate (e.g.,
one point every 2 minutes) GPS trajectories. They are either
application-logged data collected from ad-hoc location-based
queries, or generated in the scenarios where saving of energy cost
and communication cost are desired. For example, there are
60,000+ taxies in Beijing, among which many are GPS-
embedded. Since taxi drivers travel very frequently, sampling rate
has to be reduced in order to save energy consumption and
achieve reasonable response time. Unfortunately, current map-
matching approaches only deal with high-sampling-rate (typically
one point every 10-30s) GPS data, and become less effective for
low-sampling-rate points as the uncertainty in data increases.
Most existing map-matching approaches employ local or
incremental algorithms that map current or neighboring positions
onto vector road segments on a map. For an approach that only
considers current positions, the result is greatly affected by
measurement errors. The accuracy is generally low because the
correlation of neighboring points is completely overlooked. The
incremental matching algorithm in [8][7] pursues the local
matching of a small portion of the trajectory. When matching a
new position, its previous position and last matched edge are
considered. Although fast in computation, this approach‟s
performance is sensitive to the decrease of sampling frequency.
On the other hand, a global algorithm aligns entire trajectory with
the road network. Generally speaking, a global approach achieves
better accuracy at a higher computational cost. Existing global
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. To copy
otherwise, or republish, to post on servers or to redistribute to lists,
requires prior specific permission and/or a fee.
ACM GIS '09 , November 4-6, 2009. Seattle, WA, USA (c) 2009 ACM
ISBN 978-1-60558-649-6/09/11...$10.00
资源评论
