陈 煜，蒋 伟，周继恩

(中国银联股份有限公司 银联科技事业部，上海 201201)(*通信作者电子邮箱jiangwei1@unionpay.com)

0 引言

随着定位技术的发展，人们可以很容易地通过全球定位系统(Global Positioning System， GPS)设备获得移动对象的实时位置信息，从而得到移动物体的运行轨迹。由于移动对象的运行状况具有连续性，需要不断地获取GPS采样点以便更好地通过离散的采样点拟合移动对象的运行轨迹。然而较高的采样频率会产生大量的GPS记录，给轨迹数据的存储、管理和分析带来巨大的挑战[1]。为了解决这个问题，大量的轨迹压缩算法通过对数据的时空特性进行分析，通过保存那些包含重要信息的采样点[2]，如转向点、速度剧烈变化点、车辆停止点等，来达到压缩轨迹的目的。

近几年来，随着城市路网结构数据的不断完善，结合路网结构的轨迹压缩变得可行。为了降低轨迹数据的误差，首先对原始轨迹进行路网匹配(Map-Matching)预处理[3-4]。由于路网结构信息往往是静态的并且结构相对固定，因此利用路网结构信息对轨迹进行约束，不仅可以有效地降低轨迹数据的数据规模,同时可以通过路网信息降低因GPS设备精度造成的数据误差[5]。

Cao等[6]提出的Nonmaterialized算法首次提出了利用路网结构对轨迹数据进行压缩。该算法首先将轨迹采样点数据通过路网匹配算法映射在路网上，然后通过Nonmaterialized算法将映射过的轨迹数据转化为路口序列，以达到压缩轨迹的目的。Lerin等[7]对Nonmaterialized算法进行改进，通过最短路径(Shortest Path)算法和链接算法来对轨迹数据进行进一步压缩。……