基于相对同步欧氏距离筛选的在线GPS轨迹数据压缩算法

吴 青 华

(广西大学计算机与电子信息学院　广西 南宁 530004)

0　引　言

随着卫星定位技术、物联网定位技术和全球定位系统(GPS)的发展，以及各种移动终端的普及，大量的历史移动轨迹被记录下来，形成了时空轨迹数据。许多基于位置的服务LBS(Location Based Services)利用这些轨迹数据为用户提供服务。但是随着GPS轨迹数据规模的指数级增长[1]，使得在对其进行存储、传输、行为模式挖掘等方面的处理时均面临巨大挑战，加之移动设备存储设备、计算能力等限制，通常需要对采集到的轨迹数据采用压缩的方法来处理[2-3]。

GPS轨迹数据压缩旨在从各种移动设备中采集到的、具有较大冗余的原始轨迹中消除包含信息量较小的冗余点，在满足压缩后的轨迹与原始轨迹之间的相似度条件下，尽可能地减小轨迹数据量。同样的轨迹数据，经过消除冗余的压缩后，其潜在的数据挖掘速度得到极大的提高[4-5]。对于 GPS轨迹数据而言，有损压缩比无损压缩可以更大程度地减少数据量的存储[5-6], 现有的GPS轨迹数据压缩方法也以有损压缩为主[7]。通常，GPS轨迹数据的有损压缩分为离线压缩和在线压缩两种，前者需要事先明确轨迹中包含的所有轨迹点，处理的是静态的轨迹数据；后者无需事先明确轨迹中的所有轨迹点，轨迹的终点可以动态地变化，处理的是动态的轨迹数据。离线压缩方法可以把握轨迹的整体信息，获得一个全局较优的解，但不适合实时压缩的场景。在线GPS轨迹数据压缩算法可以满足实时压缩的场景，尤其对那些存储容量有限的移动设备而言，在线GPS轨迹数据压缩算法具有更好的适用性。由于存储设备和传输条件等多方面的限制，在实际应用中在线轨迹压缩算法更能够满足用户边采集边压缩的需求。

常见的GPS轨迹数据压缩方法主要是对原始轨迹进行线性拟合，把线段简化的思想运用到轨迹数据压缩中，用另一条包含更少轨迹点的轨迹曲线近似表示原始轨迹曲线，同时保证两条轨迹曲线之间的差异在一个可接受的范围内。通过此种方式在减少轨迹数据量的同时保留原始轨迹的时空特征[6-16]，达到GPS轨迹数据压缩的目的，这种方法又被称为线段简化压缩方法[3]。Douglas等[8]提出的道格拉斯-普克算法DP(Douglas-Peucker)就是一种基于线性拟合思想的经典离线GPS轨迹数据压缩算法。该算法首先以轨迹起点和轨迹终点的连线作为原始轨迹的近似轨迹，依次计算原始轨迹中各个轨迹点到该近似轨迹的垂直欧氏距离。并以垂直欧氏距离大于给定距离阈值的轨迹点作为分割点将当前轨迹段分为两部分。重复以上过程，直到所有原始轨迹点到其对应的近似轨迹段的距离均小于给定距离阈值，各分割点的序列即为压缩后的轨迹点序列。Keogh等[9]提出的开放窗口 (Open Window, OPW) 算法是在线GPS轨迹数据压缩算法的经典算法之一。该算法提供了一种窗口机制，在包含原始轨迹中部分轨迹点的窗口中进行迭代，每次迭代只关注窗口内部轨迹点的处理，通过窗口的不断迭代来实现实时轨迹数据的压缩。对于OPW算法而言，窗口的迭代条件并不唯一，可以选择窗口内的误差总和大于用户给定的最大误差阈值时进行窗口迭代；也可以选择窗口内各轨迹点对应的最大误差大于用户给定的阈值时进行窗口迭代[3,10]。DP算法和OPW算法均是以垂直欧氏距离作为压缩时距离误差的度量方式。其中，垂直欧氏距离是指轨迹点到其对应近似轨迹线段的垂线段长度。以垂直欧氏距离作为轨迹点的距离误差度量方式可以较为完整地保留轨迹点的空间特性，但轨迹数据不仅包含空间信息还包含轨迹的时间信息，垂直欧氏距离度量方式忽略了轨迹的时间信息。因此，Meratnia等[10]提出了一种新的距离误差度量方式——同步欧氏距离SED(Synchronous Euclidean Distance)代替垂直欧氏距离，将轨迹的时间信息也考虑在内，并基于SED对DP算法和OPW算法进行改进，提出了按时间比例的自顶向下压缩算法TD-TR(Top-Down Time Ratio)和按时间比例的开放窗口算法OPW-TR(Opening Window Time Ratio)。

基于上述研究背景和成果，近年来，有关GPS轨迹数据压缩的成果较多，且以在线轨迹数据压缩算法为主。Muckell等[11]提出了具有缓冲的启发式空间质量简化算法SQUISH(Spatial Quality Simplification Heuristic)算法。SQUISH算法首先初始化了一个固定长度k的优先级队列，把轨迹点依次加入到该队列中，当队列满时，删除队列中引起误差最小的轨迹点，并重新计算队列中每个轨迹点的优先级。之后，针对SQUISH算法的压缩误差没有上界、压缩轨迹与原始轨迹之间距离误差较大等问题，Muckell等[12]又对SQUISH算法进行改进，将压缩率和距离误差阈值引入到SQUISH算法中，并改进了优先级队列中轨迹点优先级的计算方式，进而提出SQUISH-E算法。SQUISH-E算法可以设定用户需要的压缩率也可以设定压缩过程中允许的最大误差距离阈值，但其在计算轨迹点优先级时，仅考虑了轨迹点所在的局部轨迹段的时空信息，不能较为准确地衡量轨迹点在当前轨迹中所携带的信息量大小。吴家皋等[13]充分考虑轨迹数据的时空信息，利用GPS数据的位置信息、时间信息、方向角和速度信息进行轨迹特征点的综合判断，从原始轨迹数据中选出包含较大信息量的轨迹点进行压缩。但此方法的压缩效果依赖于用户输入速度阈值、方向角度阈值等参数，而实际应用中用户并没有足够的经验给定合适的阈值以达到期望的压缩效果。同年，吴家皋等[14]在OPW算法的基础上进行改进，将最大偏移距离参考轨迹点作为当前待压缩的轨迹点能否被压缩的判据,降低了轨迹的压缩时间。刘磊军等[15]通过轨迹点的转向角度大小和速度变化大小来评估轨迹点信息量的大小，同时用SED限制点的偏移量,进而提出限定SED的阈值结合算法(SLTA)，以达到减小压缩轨迹与原始轨迹之间差异的目的。龙浩等[16]针对现有轨迹数据压缩算法难以确定压缩阈值的问题，对DP算法进行改进，提出了自适应参数的轨迹压缩算法。

SQUISH-E算法和OPW-TR算法是目前压缩效果较好的在线压缩算法，代表了线段简化轨迹压缩方法中在线GPS轨迹数据压缩的两个研究方向[3,5]。现有在线GPS轨迹数据压缩算法(如：SQUISH-E算法、OPW-TR算法、SLTA算法)中，除SQUISH_E算法外，大部分算法(如：OPW-TR算法、SLTA算法)都需要用户给定一个或多个特定的阈值，如：可接受的最大误差距离阈值、最大角度阈值、最大速度阈值等。而实际应用中，用户并没有足够的经验可以设置合适的阈值来达到期望的压缩率。此外，大多现有在线GPS轨迹数据压缩的算法，如SQUISH-E[12]、OPW-TR算法[9]等均是通过轨迹点所处的局部轨迹段的时空信息来衡量轨迹点在轨迹全局中所占的信息量大小[3]，不能够较为准确地衡量轨迹点在当前存储轨迹全局中的信息量，可能存在因轨迹点信息量衡量不当，导致压缩轨迹与还原轨迹之间产生较大差异的问题。针对上述问题，本文提出一种以压缩率为压缩依据，且考虑当前存储队列中所有轨迹点时空信息的在线GPS轨迹数据压缩算法-基于相对SED筛选RSF(Relative SED Filtering)的轨迹数据压缩算法。该算法首先初始化一个存储队列，每次将新到来的轨迹点添加到存储队列中。当存储队列长度超过当前情况下压缩率所允许的最大长度时，结合当前存储队列中轨迹数据对应的轨迹整体走势，借鉴TD_TR算法的思想从当前存储队列中筛选出引起SED误差相对较小的轨迹点，并将其从存储队列中移除，保证在给定压缩率下，压缩轨迹与原始轨迹之间具有较小的差异。

1　相关概念

定义1近似轨迹、近似轨迹段。线段简化压缩算法是通过使用一条包含较少轨迹点的轨迹点序列来近似表示原始轨迹点序列，而这条包含较少轨迹点的轨迹就称为原始轨迹的近似轨迹。近似轨迹中两个相邻轨迹点连接所形成的轨迹段称为其对应原始轨迹的近似轨迹段。

如图1所示，S、P1、P2、P3、P4、E表示原始轨迹中6个相邻的轨迹点。而近似轨迹中只存储了S、E两个轨迹点。即用轨迹段SE近似表示原始轨迹中轨迹点S到轨迹点E的这段轨迹，SE就称为原始轨迹中S到E这段轨迹的近似轨迹。

图1　近似轨迹

定义2同步欧氏距离SED(Synchronous Euclidean Distance)[10]。同步欧氏距离是指原始轨迹数据中的轨迹点与其在近似轨迹段上按其时间比例所求得的对应位置之间的欧氏距离。

如图2所示，P′是轨迹点P2在其相应的近似轨迹段上按时间比例的对应位置，P2P′即为轨迹点P2对应的同步欧氏距离。P″是轨迹点P2在近似轨迹段SE上的垂足，P2P″即为轨迹点P2到其对应的近似轨迹段SE的垂直欧氏距离。

图2　SED和垂直欧氏距离

(1)

(2)

由轨迹点P2和P′的位置信息可以计算出P2的同步欧氏距离:

(3)

通过式(1)、式(2)可以看出SED的度量方式考虑了轨迹数据的空间信息和时间信息。

2　基于相对SED筛选的在线GPS轨迹数据压缩算法

压缩率一定时，如何在有限的存储空间内选择包含更多轨迹时空信息的轨迹点进行存储是在线GPS轨迹数据压缩算法的关键。换而言之，在一定压缩率要求下，在线GPS轨迹压缩算法的关键就是随着新轨迹点的不断加入，如何从当前存储队列中选出引起SED误差最小的轨迹点进行移除。由于在线GPS轨迹压缩算法所压缩的轨迹的终点是不确定的，当新的轨迹点到来时，存储队列中的其他轨迹点所携带的轨迹信息量会随着新轨迹点的时空信息发生变化。因此，从当前存储队列中轨迹整体走势的角度来衡量存储队列中各个轨迹点的信息量相比于仅从轨迹点所处局部轨迹段的角度考虑轨迹点信息量更加准确。

TD-TR算法作为离线轨迹数据压缩领域的经典算法，其压缩过程把握了轨迹的全局走势，每次将包含轨迹信息量较大的轨迹点作为轨迹的分割点，进行存储，较在线GPS轨迹数据压缩算法只考虑轨迹点所在局部轨迹段的方式能够更准确地衡量轨迹点所携带的轨迹信息量。RSF算法借鉴TD-TR算法的思想，当存储队列长度超过一定限制时，对存储队列中的轨迹点信息量进行衡量，以筛选出存储队列中包含轨迹信息量较小的轨迹点。

RSF算法以用户期望达到的压缩率为依据对在线GPS轨迹数据进行压缩，算法步骤可以简单描述为：

(1) 首先初始化一个存储队列，将每一个新到来的轨迹点加入到存储队列中。

(2) 当存储队列长度超过当前情况下压缩率所允许的最大长度时，利用TD-TR算法的思想，从当前存储队列中标记出包含轨迹信息量较小的轨迹点。

(3) 从这些信息量较小的轨迹点中选择引起SED误差相对较小的轨迹点进行移除，而非像TD-TR算法那样，根据一个用户输入的固定距离阈值来判定轨迹点的去留。

随着轨迹点的不断到来，重复以上过程，即可实现GPS轨迹数据的在线压缩。存储队列中的轨迹点序列即为压缩后的轨迹点序列。

RSF算法的具体过程如算法1的伪代码所示，其中，SaveQueue表示存储队列，存储的是需要被存储的轨迹点信息，信息格式与压缩前的轨迹点信息格式一致，包含经纬度信息和时间信息；|SaveQueue|表示SaveQueue队列的长度；LIPS(Little Information Point Select)算法是一个轨迹点选择算法，目的是从当前存储队列中标记出包含轨迹信息量较小的轨迹点，返回值为标记序列signSeq[]；CalcSED()是一个SED距离计算算法，计算方法如式(3)所示。

算法1RFS算法

输入：原始轨迹数据T、压缩率ratio。其中，T={P1,P2,…,Pn}={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)};

输出：压缩轨迹数据T′。其中，T′={P1,Pi1,Pi2,…Pn},P1,Pi1,Pi2,…,Pn∈T，P1,Pi1,Pi2,…,Pn是经压缩之后保留的轨迹点，称为原始轨迹数据中的关键轨迹点。

Begin

1) |SaveQueue|←2//将轨迹点存储队列的大小初始化为2

2) foreachnewPointPi

3)SaveQueue←Pi;

4)maxLen←(i*ratio);

5)If |SaveQueue|>maxLen

6)signSeq[]←LIPS(SaveQueue);

7)foreachpointPinsignSeq[]

//j为轨迹点P在SaveQueue中的编号

8)CalcSED(Pj-1,Pj,Pj+1);

9)Endfor

10)SelectminSEDPointremovefromSaveQueue

11)end If

12) Endfor

End

如算法1所示，首先初始化一个大小为2的存储队列(步骤1)，对于每一个新采集到的轨迹点Pi，将Pi存入存储队列中去(步骤2-3)，计算当前允许的存储队列最大长度,其中i为当前采集到的轨迹点总数(步骤4)。若当前存储队列长度大于当前压缩率所允许的存储队列最大长度，则通过LIPS算法，得到当前存储队列中包含轨迹信息量最少的轨迹点标记序列(步骤6)。对标记序列中的每个点计算其相对于存储队列中前后相邻轨迹点的SED(步骤7-9)，从中选择最小SED值对应的轨迹点，将其从存储队列中移除(步骤10)，保证压缩结果达到给定的压缩率的同时尽可能地减小因删除轨迹点而引起的误差。

如算法2所示，LIPS算法首先以存储队列中的第一个轨迹点和最后一个轨迹点作为存储队列中所有轨迹点所表示的原始轨迹的近似轨迹。然后依次计算轨迹中各点到该近似轨迹的SED距离，并以最大SED距离对应的轨迹点作为原始轨迹的分割点，将原始轨迹分割成两条子轨迹(步骤7-8)。递归进行此操作(步骤9-10)，直到子轨迹中包含的轨迹点数不超过3为止。将包含3个轨迹点的子轨迹段对应的中间轨迹点Pj进行标记，加入到标记序列中。因为，按照TD-TR算法的规则，当子轨迹中只包含3个轨迹点时，其对应的中间轨迹点所包含的轨迹信息量相对于其他2个轨迹点而言是比较小的，也就是说若将子轨迹段的中间轨迹点从存储队列中移除，其引起的误差是较小的。LIPS算法的返回结果为轨迹点标记序列。

算法2LIPS算法

输入：存储队列SaveQueue,其中，SaveQueue={Pj1,Pj2,…,Pjm}={(xj1,yj1,tj1),(xj2,yj2,tj2),…,(xjm,yjm,tjm)}

输出：标记序列signSeq[]

Begin

1) If |SaveQueue|=3

2)FlagthemiddlepointinsignSeq[]

3) Else if |SaveQueue|>3

4)foreachPointPjxinSaveQueue,(1

5)CalcSED(Pj1,Pjx,Pjm);

6)Endfor

7)SelectPointPjwhichPjhasmaxSED

8)createtwosub-Trajectory

9)LIPS(sub-Tra1);

10)LIPS(sub-Tra2);

11) end If

12) returnsignSeq[];

End

RSF算法在存储的轨迹点个数超过当前情况下压缩率所允许的最大个数时，从当前存储队列中轨迹全局的角度，衡量每个轨迹点所携带的轨迹时空信息量，将包含轨迹信息量较大的轨迹点保留在存储队列中，尽可能减小压缩轨迹与原始轨迹之间的差异。下面从理论分析和实验验证两个方面验证RSF算法的有效性。

3　算法分析及其性能度量指标

3.1　算法分析

目前GPS轨迹数据在线压缩方法中的主流算法有SQUISH-E算法和OPW算法的改进算法OPW-TR算法等。其中，OPW-TR算法需要设置最大误差距离阈值进行轨迹数据的压缩，SQUISH-E算法可以设置所需要的压缩率(ratio)也可以设置最大误差距离阈值。由于以最大误差距离阈值为参数的压缩算法需要用户具有足够的经验给定阈值才可能达到预期的压缩效果，所以以压缩率为依据的轨迹数据压缩算法适用性更强。RSF算法是以用户需要的压缩率(ratio)为参数进行轨迹数据压缩的，所以下面主要将RSF算法与可设置压缩率的SQUISH-E算法进行对比。为了方便表述，本文将以ratio作为输入参数的SQUISH-E算法记为SQUISH-E(ratio)算法。

RSF算法和 SQUISH-E(ratio)算法均是从原始轨迹数据中选择部分关键轨迹点进行存储。SQUISH-E(ratio)算法在筛选关键轨迹点时，通过轨迹点自身的优先级进行筛选，轨迹点的优先级包含当前轨迹点自身到前后关键点所形成近似轨迹段的SED距离，以及曾经的邻居轨迹点被删除时累加到自身的优先级两个方面。只考虑了局部轨迹点信息，没有考虑当前存储队列中全部的轨迹信息，且由于轨迹点被删除之后，其邻居轨迹点相对于其前后轨迹点的SED距离已经发生了变化，此时再将删除点的优先级直接累加到邻居轨迹点的优先级上来衡量邻居轨迹点的信息量可能存在一定偏差。RSF算法结合TD-TR算法的思想，将每个子轨迹段中最后作为分割点的轨迹点标记出来，从当前存储队列对应轨迹全局的角度考虑了存储队列中每个轨迹点的信息量。最后，统一用存储队列中该轨迹点相对于其前后相邻轨迹点的SED距离选出引起误差最小的轨迹点进行删除。在保证达到一定压缩率要求的前提下，尽可能地保留了包含轨迹时空信息量较大的轨迹点，进而达到减小压缩后的轨迹与原始轨迹之间差异的目的。

3.2　算法性能度量指标

就压缩算法而言，数据经过压缩之后所带来的存储空间的节省和能够达到的还原精度是压缩算法重要的性能指标。GPS轨迹数据压缩算法的性能可以从压缩率、恢复效果和压缩速度三个方面来衡量[17-18]。本文用轨迹数据压缩后所节省的存储空间和原始GPS轨迹数据大小的比值来表示压缩率信息；用压缩轨迹产生的平均SED误差来衡量压缩后轨迹的还原轨迹与原始轨迹之间的误差[18]，此误差越小，表示压缩后的轨迹数据所能达到的还原精度越高；用GPS轨迹数据压缩算法的压缩时间来衡量其压缩速度。

压缩率和平均SED误差的定义如下：

定义3压缩率[18]。压缩率指压缩后数据较原始数据所节省的存储空间大小与原始数据所占存储空间大小的比值。

式(4)给出了压缩率的计算方式。其中，CR为压缩率(Compression Ratio)，S1和S2分别表示压缩后和压缩前的轨迹数据大小。仅考虑压缩率的情况下，压缩率越高,压缩算法的压缩效果越好。

(4)

定义4平均SED误差[12]。平均SED误差是指原始轨迹中被舍弃的轨迹点与还原轨迹中对应位置的平均误差，反映了还原轨迹和原始轨迹之间的差距。

式(5)给出了平均SED误差的计算方式。其中SED(pi)指原始轨迹中的第i个轨迹点与其在压缩轨迹中对应的轨迹点之间的欧氏距离，n为原始轨迹中轨迹点的个数。

(5)

4　实验与分析

为了进一步验证RSF算法的有效性，在理论分析的基础上通过实验进行对比分析。这里仍将在线GPS轨迹数据主流压缩算法中以压缩率为输入参数的SQUISH-E(ratio)算法作为RSF算法的对比算法，根据实验结果，从压缩率、平均SED误差和压缩时间三个方面进行对比分析，并给出相应结论。

4.1　实验环境和数据

本次实验中的算法程序通过Java语言编写，使用eclipse开发工具,实验环境为：Intel(R) Corei7处理器,主频2.6 GHz,Win7操作系统,物理内存4 GB。

实验数据采用的是微软亚洲研究院发布的公开轨迹数据集Geolife[19]，数据包括了182名志愿者5年的轨迹，共17 621条轨迹，总距离达到129 295公里，总时长达到50 176小时，采集设备各不相同，采样率也有差异，但91%以上的是高密度的采样，如：1～5秒或5～10米。Geolife数据集包含的信息巨大，本次实验的目的是为了验证RFS算法的有效性，对轨迹数据量的大小并没有过多要求，固不需要轨迹数据集合中的全部信息，本文从编号为“000”的Geolife轨迹数据中选取了一条包含轨迹点数目较多的轨迹进行实验。该轨迹由1 103个轨迹点组成，轨迹点信息由经纬度信息、时间戳信息、海拔高度等7个字段的信息组成。表1给出了某轨迹点的描述信息。

表1　轨迹点信息

其中，字段“天数”指的是距离1899年12月30日的天数(包括小数部分)。根据“天数”字段的值可以计算出相应的“日期”和“时间”字段信息。根据常用的轨迹数据查询类型可知，轨迹的经纬度信息和时间信息是人们较为关心的[16]，因此，在进行实验时，本文仅从原始轨迹中选取经纬度信息和天数信息三个字段的数据作为实验的输入数据。以下为实验输入数据中1个轨迹点的描述信息，以逗号分隔的三个字段分别代表轨迹点的纬度信息、经度信息和时间信息：

40.010 6,116.322 961,39 925.110 405 092 6

4.2　实验结果分析

由于RSF算法和SQUISH-E(ratio)算法均以用户期望达到的压缩率ratio作为压缩时的依据。图3为RSF算法和SQUISH-E(ratio)算法在不同压缩率下产生的平均SED误差对比图。图4为RSF算法和SQUISH-E(ratio)算法在不同压缩率下所消耗的压缩时间对比图，该运行时间取的是各算法运行10次时间的平均值。其中，用于输入的期望压缩率ratio∈[0,1)，压缩率等于0时，压缩后的轨迹数据与压缩前的轨迹数据相同。随着压缩率的增大，压缩后的轨迹数据越来越小，包含的轨迹点也越来越少。极端情况下，一条轨迹压缩后仅包含轨迹的起点和终点两个轨迹点，但达不到压缩率等于1的情况。

图3　不同压缩率下的平均SED误差对比

图4　相同压缩率下的压缩时间对比

由图3可以看出平均SED误差随着压缩率的增高而不断增大。在相同压缩率下，RSF算法对应的平均SED误差始终小于SQUISH_E(ratio)。此外，随着压缩率的增加，两算法平均SED误差的差距呈增大趋势。当ratio<0.5时，SQUISH_E(ratio)算法与RSF算法在相同压缩率下，平均SED误差平均相差约0.53 m。当ratio>0.5时，SQUISH_E(ratio)算法与RSF算法在相同压缩率下，对应的平均SED误差平均相差约1.54 m，相对于压缩率小于0.5时，平均SED误差的差距增加了近2倍。这主要是由于随着压缩率的增加，相同原始轨迹点数下，能够保存的轨迹点个数越来越少，删除的轨迹点引起的误差也越来越大，这时关键轨迹点的选择也就尤为重要，RSF算法的优势也就越来越明显。

由图4为相同压缩率下两算法所需压缩时间的对比图，从图中可以看出RSF算法所需的压缩时间较SQUISH_E(ratio)算法所需的压缩时间更长，且RSF算法在压缩率取0.3～0.7时所需的压缩时间较长，在压缩率为0.4时达到峰值478 ms。这主要是由于当轨迹存储队列长度大于ratio下所允许的最大长度时，RSF算法需对队列中的所有轨迹点进行一次LIPS算法操作，从当前存储队列对应轨迹全局的角度考虑之后筛选出引起误差最小的轨迹点进行删除。而SQUISH_E(ratio)算法则只需比较轨迹队列中每个轨迹点在局部轨迹段的优先级，即可选出将要被删除的轨迹点。所以RSF算法在压缩过程中所需的计算量更大，相应的运行时间也就越长。此外，对于RSF算法而言，当压缩率较高时(如0.9)，由于其可允许的存储队列长度较小，每次在选择要删除的轨迹点时，其计算量也大大降低，相应的压缩时间也就越短；当压缩率较低时(如0.1)，由于其可允许的存储队列长度较大，需要删除的轨迹点较少，其计算次数较压缩率较低时明显减少，相应的压缩时间也就越短；当压缩率适中时(如0.4)，其所需的计算次数和计算量都相对较多，所需的压缩时间也较长，因此如图4所示，压缩率适中时，RSF算法所需的压缩时间较长。

综合以上理论分析和实验结果，在相同压缩率下，RSF算法对应的平均SED误差较SQUISH_E(ratio)算法对应的平均SED误差更小，相应的，RSF算法对应的还原轨迹比SQUISH_E(ratio)算法对应的还原轨迹具有更高的还原精度。此外，RSF算法较SQUISH_E(ratio)算法所需的压缩时间相对较长，对于在线GPS轨迹数据压缩算法而言，一定压缩率前提下，在可接受的压缩时间内获得更高的轨迹还原精度是值得的。

5　结　语

本文针对现有在线GPS轨迹数据压缩算法中存在的压缩率一定时，压缩轨迹与原始轨迹之间差异较大的问题提出了一种基于相对SED筛选的在线GPS轨迹数据压缩算法。该算法以用户期望达到的压缩率为依据，进行轨迹数据的压缩。当存储的轨迹点个数超过压缩率要求时，利用TD-TR算法的思想考虑当前存储队列中所有轨迹点的时空信息，从当前存储队列中删除引起SED误差最小的轨迹点，尽可能地保证包含轨迹时空信息量较大的轨迹点被保留在存储队列中，以达到减小压缩后的轨迹与原始轨迹之间时空信息差异的目的。理论分析和实验结果表明，较现有以压缩率为压缩依据的主流在线GPS轨迹数据主流压缩算法而言，RSF算法可以在给定压缩率的限制下，以一定的压缩时间为代价，获得更小的平均SED误差距离，进而得到与原始轨迹更接近的压缩轨迹。在将来的研究中，将针对RSF算法的压缩时间进行进一步优化，以期设计出更有效的GPS轨迹数据压缩算法。

[1] 许佳捷，郑凯，池明旻,等.轨迹大数据:数据、应用与技术现状[J]. 通信学报,2015,36(12):97-105.

[2] Zheng Y, Zhou X. Computing with Spatial Trajectories[M]. Springer New York, 2011.

[3] 江俊文，王晓玲. 轨迹数据压缩综述[J]. 华东师范大学学报(自然科学版),2015(5):61-76.

[4] Jeung H, Man L Y, Jensen C S. Trajectory Pattern Mining[M]// Computing with Spatial Trajectories. Springer New York, 2011:330-339.

[5] 樊庆富，张磊，刘磊军,等.基于偏移量计算的在线GPS轨迹数据压缩[J].计算机工程与应用,2016,52(3):1-7.

[6] Chen M, Xu M, Franti P. Compression of GPS Trajectories[C]//Data Compression Conference. IEEE, 2012:62-71.

[7] Chen M, Xu M, Franti P. Compression of GPS trajectories using optimized approximation. [C]//Proceeding of the 2012 21st International Conference on Pattern Recognition. Piscataway, NJ: IEEE, 2012, 3180-3183.

[8] Douglas D H, Peucker T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J]. Cartographica the International Journal for Geographic Information & Geovisualization, 2001, 10(2):112-122.

[9] Keogh E J, Chu S, Pazzani M J. An Online Algorithm for Segmenting Time Series[C]// IEEE International Conference on Data Mining. IEEE Computer Society, 2001:289-296.

[10] Meratnia N, By R A D. Spatiotemporal Compression Techniques for Moving Point Objects[M]// Advances in Database Technology-EDBT 2004. Springer Berlin Heidelberg, 2004:765-782.

[11] Muckell J, Hwang J H, Patil V, et al. SQUISH: an online approach for GPS trajectory compression[C]//Proceedings of the 2nd International Congference on Computing for Geospatial Research & Applications. New York:ACM,2011:13.

[12] Muckell J, Olsen P W, Hwang J H, et al. Compression of trajectory data: a comprehensive evaluation and new approach[J]. GeoInformatica, 2014, 18(3):435-460.

[13] 吴家皋,钱科宇,刘敏,等.基于综合时空特性的混合式轨迹压缩算法[J]. 计算机应用, 2015, 35(5):1209-1212.

[14] 吴家皋, 刘敏, 韦光,等. 一种改进的滑动窗口轨迹数据压缩算法[J]. 计算机技术与发展, 2015, 25(12):47-51.

[15] 刘磊军，房晨，张磊,等. 基于运动状态改变的在线全球定位系统轨迹数据压缩[J].计算机应用，2016，36(1):122-127.

[16] 龙浩,张书奎,孙鹏辉. 自适应参数的轨迹压缩算法[J/OL]. 计算机应用研究,优先出版,2018，35(3). http://www.arocmag.com/article/02-2018-03-026.html.

[17] 吴佩莉.移动对象轨迹数据管理关键技术研究[D].北京：北京理工大学,2015.

[18] 冯神柱.路网轨迹数据的压缩存储技术研究[D].杭州：杭州电子科技大学，2013.

[19] Zheng Y, Xie X, Ma W Y. GeoLife: A Collaborative Social Networking Service among User, Location and Trajectory[J]. Bulletin of the Technical Committee on Data Engineering, 2011, 33(2):32-39.