面向轨迹大数据的压缩空间算法研究
来源:用户上传
作者:王伟
摘要：大量定位技术和移动技术的成熟为多源、多模态数据的增加奠定了基础，其中有关运动物体轨迹的GPS轨迹数据增长尤为突出。因此，提出了一种路网轨道压缩算法。首先，在预处理步骤中，将轨迹分解为空间路径和时间序列。其次，在压缩步骤中，设计对空间路径执行空间压缩的算法，以及对时间序列并行执行时间压缩的算法。
关键词：路网;空间压缩算法;时间压缩算法
中图分类号：TP311.13 文献标识码：A
文章编号：1009-3044（2020）33-0039-02
开放科学（资源服务）标识码（OSID）：
存储或传输大量由位置采集技术产生的轨迹数据是非常具有挑战性的。在一些研究中通过减少轨迹数据中的位置点的信息冗余大幅度减少存储需求和通信负载[1]。压缩方法通常需要在压缩比和最大误差之间进行了权衡，一般来说，压缩比越高，压缩轨迹数据的质量就越差，反之亦然。如果相应的轨迹应用或者相应用户能够容忍一定范围内的轨迹误差，trajic算法是一种很合适的算法，其在一定误差范围内可以获得相对良好的压缩比。它具有预测下一位置点数据的预测器，以及一个产生小残差的残差编码方案，该方案可用于补偿预测值和实际值之间差异。
1 问题模型与符号定义
传统的方法通过n个三元组的序列表示一个轨迹r，其形式类似（< x1，y1，t1>，，…，），其中记录移动物体的经度和纬度，而￡;则表示移动物体处于当前位置的时间。
轨迹分解作为轨迹压缩的第一步，从而为轨迹压缩奠定基础。COMPRESS轨迹压缩算法是基于道路网络实现的，为此首先将路网建模为有向图G=（V，E），其中v是顶点集合，E是边集合。边e上的权重被表示为w（e），可以是物理距离、旅行时间或其他成本，具体取决于不同的应用环境。轨迹是运动物体随时间在空间中的运动痕迹。因此，它包含空间信息和时间信息[2]。
原始轨迹数据三元组说明了移动对象在时间ti时，位于的位置。假设为轨迹的起点，如果已知第i个点的位置，那么从起始点到第i个点的距离di必是确定的，但如果我们知道移动物体从时间t1到ti的距离di，对应于时间戳ti的位置却是无法确定的。因此，轨迹分解记录轨迹T所经过的空间路径，并根据di计算转换回，其中表示的移动物体在轨迹T中所经过的m条边的序列。如此一来算法只需要压缩边的序列即可，这更意义实现，压缩效率也会更高。
2 基于最短路径的空间压缩算法
3 时间序列压缩算法
传统方法中，时间同步欧氏距离（ Time Synchronized Euclid-ean Distance，TSED）是用于評估误差上限的重要度量。与TSED不同，本文提出两种新的误差评估度量一时间同步网络距离（ Time Svnchronized Network Distance，TSND）和网络同步时间差异（Network Synchronized Time Difference，NSTD），其定义如下：
定义1：TSND是给定一个时间序列TS，及其对应的压缩序列TS：，TNSD用于度量移动物体在两条轨迹上相同时间戳下距离的最大差异。
用于压缩时间序列的有损压缩算法需要满足以下两个核心目标：首先，压缩轨迹与原始轨迹之间的TSND和NSTD必须被限定到一定的误差值范围内，该阈值根据具体用户或者应用而决定。其次，压缩率越高越好。
1）严格贯穿折线压缩算法
轨迹分解之后，时间序列是一系列由距离和时间构成的二维元组。因此，在一个距离一时间图中可以绘制出原始的时间序列图，而任何一条轨迹的时间序列都是一条贯穿该轨迹时间序列所有点的折线。对于一个给定值为r误差TSND，那么可以围绕轨迹中n个点，并每个点为中心绘制长度为2r的垂直线段（如图1所示）。如果将这n条垂直线当成对象，然后时间序列压缩问题可以简化为一个计算几何问题，称为贯穿折线问题。该问题的本质是找到一条折线，该折线包含按顺序通过多个对象的最少定点数。如图1，从四个点压缩为3个点，其压缩率为1.33。与传统贯穿折线定义不同，本文提出新的多限制贯穿折线，其中既考虑了TSND问题也考虑了NSTD问题[3，4]。
定义3：贯穿折线是指横穿原始时间一距离折线中所有n个垂直线段和以垂直线段为中心的n个水平线段构成的矩形区域所形成的一条折线。
如图1左图所示，符合定义的贯穿折线只能保证在原始折线取样时间戳点才能保证TSND限制在r，在其他时间节点则无法保证如时间点t'。为此，给出了严格贯穿折线的定义（如图1右图所示）：
定义4：严格贯穿折线是一条所有顶点都属于原始折线顶点子集的贯穿折线。
理论研究证明搜索符合条件的严格贯穿折线并用于时间序列压缩其计算复杂度可以限制在O（n），但相应的算法无法保证获取最优解，而最优算法的计算复杂度达到了O（n2）。
2）管道贯穿折线压缩算法
如上所述，贯穿阵线压缩算法缺乏严格的限制，从而无法将压缩时间序列的TSND和NSTD误差限制在某个范围内，而严格贯穿折线压缩算法则给出了过多的限制，在保证误差范围的同时也将大量不必要的时间点引入到了压缩数据中，这降低了压缩的比率，增加了算法的计算量。基于此，管道贯穿折线压缩算法得以提出。
与贯穿折线相似，原始时间序列被映射为时间一距离空间中的一条折线，以原始折线的每一个顶点作为中心绘制长度为2τ的垂直线段。然后以连续垂直线段的上顶点和下顶点作为多边形顶点，构建一个多边形称为TSND管道Pd。原始时间序列这些位于该管道的中心，因此，只要管道贯穿折线完全位于TSND管道Pd内部，那么就可以确保压缩时间序列和原始时间序列之间的TSND误差不超过r。相较于严格贯穿折线压缩算法（3顶点），管道贯穿折线仅需要2个顶点。 根据同祥的算法逻辑，在给定一个逻辑时间误差上限11情况下可以计算获取NSTD管道P，。因此在给定距离和时间误差τ和η的情况下，综合TSND和NSTD度量可以获得一个综合管道P=PtUPd。因此管道贯穿折线压缩算法的核心可以表述为找到一条折线該折线完全位于管道P内且具有最少的顶点。
基于上述论述，TSND管道、NSTD管道和综合管道的定义介绍如下：
定义5：TSND管道是给定一个时间序列以及相应的TSND误差限制τ，则相应的TSND管道Pd是包含2n个顶点的多边形。
定义6：NSTD管道是给定一个时间序列以及相应的NSTD误差限制η，则相应的NSTD管道P。是一个包含2n个顶点的多边形。
定义7：综合管道是给定一个时间序列以及TSND和NSTD误差分别为τ和η，而Pd和Pt分别表示TSND管道和NSTD管道，那么Pd与Pt的交叉形成的归为称为综合管道P（P=PtU Pd）。
定义8：综合管道贯穿折线是给定一个时间序列及其相应的综合管道P，则综合管道贯穿折线就是完全位于该管道内的一条折线，该折线连接了（d，，t1）与（dn，tn）。
4 对比实验
图3（a）给出了在不同取样率下的压缩率，结果显示取样率对于压缩率影响相对要少得多，在取样率从1秒/点到60秒/点的变化过程中，本文提出的空间压缩算法的平均压缩率是1.52，这与最高压缩率比较接近。在图3（b）中展示了在不同子序列长度阈值下对空间路径的压缩比率。这里压缩率是指经过第二阶段压缩后得到的轨迹与第一阶段空间压缩后的轨迹之间的比率。
贪婪RSLC和TSLC都是线性算法，但RSLC（DP）的时间复杂度为O（n2）。如图4所示，RSLC（ DP）压缩包含108个时态元组的训练集比TSLC和RSLC贪婪实现花费的时间要长得多。与贪婪（greedY）实现的RSLC相比，TSLC更加耗时，因为当误差范围很小时，多边形包含更多的边。但是，多边形的边缘不会超过4n+4，因此可以保证TSLC的效率。另一方面，贪婪的RSLC总是运行得很快，因为它只需扫描时间序列中的n个点。
5 结论
本文设计了一种实用的轨迹分解方法，将空间数据与时间数据分开，实现了轨迹数据的降维处理。在此基础之上，提出了充分考虑时空特征的轨迹大数据压缩算法。最后，实验结果表明了算法在压缩比和压缩质量指标上的优势。本栏目责任编辑：王力
参考文献：
[1]梁明，陈文静，段平，等.轨迹压缩的典型方法评价[J].测绘通报，2019（4）：60-64.70.
[2]王伟谭松荣.基于轨迹大数据离线挖掘与在线实时监测的出 租车异常轨迹检测算法[J].数字技术与应用，2018（12）：118-119.
[3]张玺君，袁占亭，张红，等，交通轨迹大数据预处理方法研究[J].计算机工程，2019，45（6）：26-31.
[4]冯慧芳，柏凤山，徐有基.基于轨迹大数据的城市交通感知和路网关键节点识别[J].交通运输系统工程与信息，2018，18（3）：42-47，54.
【通联编辑：张薇】
作者简介：王伟（1982-），女，河南林州人，本科，讲师，研究方向：大数据分析、人工智能系统。
转载注明来源:https://www.xzbu.com/8/view-15387690.htm
