10-周建华-Map-Matching for Low-Sampling-Rate GPS Trajectories1

preview
试读
10页
需积分: 0 2 下载量 196 浏览量 更新于2022-08-04 收藏 693KB PDF 举报
Map匹配是将用户位置观测序列与数字地图上的道路网络对齐的过程，它是移动对象管理、交通流量分析和导航等应用的基础预处理步骤。在实际应用中，存在大量低采样率（例如，每2-5分钟一个点）的GPS轨迹。然而，大多数当前的Map匹配方法仅处理高采样率（通常为每10-30秒一个点）的GPS数据，对于低采样率数据，由于数据不确定性增加，其效果会降低。 本文提出了一个新颖的全局Map匹配算法，称为ST-Matching，专门针对低采样率GPS轨迹。ST-Matching考虑了两个关键因素：(1)道路网络的空间几何和拓扑结构，以及(2)轨迹的时间/速度约束。基于空间-时间分析，从这些因素构建了一个候选图，然后从中识别出最佳匹配路径序列。 ST-Matching算法与增量算法和基于平均Fréchet距离(AFD)的全局Map匹配算法进行了比较。实验在合成数据集和真实数据集上进行。结果显示，对于低采样率轨迹，我们的ST-Matching算法在匹配精度上显著优于增量算法。同时，与AFD为基础的全局算法相比，ST-Matching不仅提高了准确性，还缩短了运行时间。 根据计算机科学分类，该研究涉及H.2.8[数据库应用]：空间数据库和GIS领域。主要涉及的通用术语包括算法设计。关键词包括Map匹配、低采样率GPS轨迹、ST-Matching、空间-时间分析、几何拓扑结构、速度约束、算法性能和效率。 ST-Matching算法的创新之处在于其能够有效处理数据不确定性，利用空间和时间信息来提高匹配的准确性和效率。通过构建候选图并考虑时间约束，它能够更精确地确定车辆在道路网络中的实际路径，这对于实时交通管理和分析至关重要。此外，与现有的全局和局部算法相比，ST-Matching在处理低采样率数据时展现出更好的性能，这使得它在处理大量低质量GPS数据的应用中具有优势。 这项研究为处理低采样率GPS轨迹的Map匹配问题提供了一种有效的方法，对于提升交通监控、智能交通系统以及位置服务的性能具有重要意义。未来的研究可能进一步探索如何优化ST-Matching算法，以适应更多复杂情况，例如动态变化的道路网络或更高的数据不准确性。
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

下载后可阅读完整内容，剩余9页未读，立即下载

资源推荐
资源评论