计算机应用   2017, Vol. 37 Issue (5): 1282-1286, 1330  DOI: 10.11772/j.issn.1001-9081.2017.05.1282
0

引用本文 

吴家皋, 夏轩, 刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用, 2017, 37(5): 1282-1286, 1330.DOI: 10.11772/j.issn.1001-9081.2017.05.1282.
WU Jiagao, XIA Xuan, LIU Linfeng. Parallel trajectory compression method based on MapReduce[J]. Journal of Computer Applications, 2017, 37(5): 1282-1286, 1330. DOI: 10.11772/j.issn.1001-9081.2017.05.1282.

基金项目

国家自然科学基金资助项目(61373139,41571389,71301081);东南大学计算机网络和信息集成教育部重点实验室开放基金资助项目(K93-9-2014-05B);南京邮电大学科研基金资助项目(NY214063)

通信作者

吴家皋, 电子邮箱 jgwu@njupt.edu.cn

作者简介

吴家皋 (1969-), 男, 江苏苏州人, 副教授, 博士, CCF会员, 主要研究方向:移动网络、云计算, E-mail: jgwu@njupt.edu.cn;
夏轩 (1989-), 男, 江苏宿迁人, 硕士研究生, 主要研究方向:云计算、移动模型;
刘林峰 (1980-), 男, 江苏丹阳人, 副教授, 博士, CCF会员, 主要研究方向:水下传感器网络

文章历史

收稿日期:2016-11-07
修回日期:2016-12-14
基于MapReduce的轨迹压缩并行化方法
吴家皋1,2, 夏轩1, 刘林峰1,2    
1. 南京邮电大学 计算机学院, 南京 210003;
2. 计算机网络和信息集成教育部重点实验室 (东南大学), 南京 211189
摘要: 带有全球定位系统(GPS)功能设备的增多,产生大量的时空轨迹数据,给数据的存储、传输和处理带来了沉重的负担。为了减轻这种负担,各种轨迹压缩方法也随之产生。提出了一种基于MapReduce的并行化轨迹压缩方法,针对并行化导致的分段点前后轨迹的相关性被破坏的问题,首先,采用两种分段点相互交错的划分方法划分轨迹;然后,将分段轨迹分配到多个节点上进行并行化压缩;最后,对压缩结果进行匹配合并。性能测试分析结果表明,所提出的并行化轨迹压缩方法能够大幅提高压缩效率,而且能完全消除因分段导致分段点前后相关性被破坏带来的误差。
关键词: 轨迹压缩    分布式存储    MapReduce    Hadoop    全球定位系统轨迹    
Parallel trajectory compression method based on MapReduce
WU Jiagao1,2, XIA Xuan1, LIU Linfeng1,2     
1. School of Computer, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China;
2. Key Laboratory of Computer Network and Information Integration of Ministry of Education (Southeast University), Nanjing Jiangsu 211189, China
Abstract: The massive spatiotemporal trajectory data is a heavy burden to store, transmit and process, which is caused by the increase Global Positioning System (GPS)-enable devices. In order to reduce the burden, many kinds of trajectory compression methods were generated. A parallel trajectory compression method based on MapReduce was proposed in this paper. In order to solve the destructive problem of correlation nearby segmentation points caused by the parallelization, in this method, the trajectory was divided by two segmentation methods in which the segmentation points were interleaving firstly. Then, the trajectory segments were assigned to different nodes for parallel compression. Lastly, the compression results were matched and merged. The performance test and analysis results show that the proposed method can not only increase the compression efficiency significantly, but also eliminate the error which is caused by the destructive problem of correlation.
Key words: trajectory compression    distributed storage    MapReduce    Hadoop    Global Positioning System (GPS) trajectory    
0 引言

在许多城市,人们驾驶装备了全球定位系统 (Global Positioning System, GPS) 设备的探测车沿着道路行进来收集轨迹数据,这些数据可以被应用在很多领域,例如交通信息服务、导航服务、公交车到达时间服务等[1-2]。GPS轨迹数据包含着海量的数据信息。据统计,假设GPS每隔5 s采集一次信息,那么1辆车一天就需要大概70 MB的存储空间,而一个城市所有车辆需要的存储空间将非常庞大,对如此庞大数据的查询、分析和传输是极具挑战性的,因此对GPS轨迹数据压缩的研究成为这一领域的热点。

在对移动轨迹进行存储时,其实只需要存储能够准确描述移动轨迹信息的点,其他的轨迹点可以作为冗余轨迹点舍弃掉。而轨迹压缩的目的就是在保留数据包含的信息的前提下,尽可能地减少数据量,也就是说当输入一条轨迹,通过轨迹压缩方法[3]可以输出一条占用更少空间的压缩轨迹,而压缩轨迹与原始轨迹之间的误差必须是在可以接受的范围内。

随着轨迹数据规模的爆炸式增长,集中式轨迹压缩方法将会受到性能瓶颈制约,因此,迫切需要一种技术来解决庞大的轨迹数据带来的难题。面对这种难题,云计算提供了可观的前景来应对这些急剧增长的数据量; 同时,目前对于大规模的分布式存储和云计算的研究也比较多,例如:谷歌文件系统 (Google File System, GFS)[4]、MapReduce[5]、Map-reduce-merge[6]、Dryad[7]、Pig latin[8]等。最近,尤其是GFS和Map-Reduce架构在大数据分析方面性能相对优越,因此在世界范围内引起了越来越多的关注。Hadoop MapReduce为大数据处理提供了一个很好的平台,它主要运用的是“分而治之”的思想,目的就是将任务分给好多个节点去处理,提高处理效率,因此,可以将原始轨迹分段分给多个节点进行压缩处理,但是将轨迹压缩任务并行化却会导致分段点前后轨迹的相关性被破坏。

针对上述问题,本文研究提出了一种基于MapReduce的并行化轨迹压缩方法。该方法首先将一条轨迹数据按照两种方式分段,并且使得这两种分段方式的分段点相互错开;其次将每一段划分到不同节点上并行压缩;最后将两种划分的轨迹数据压缩结果相互匹配合并,以此来消除因分段带来的误差。实验结果表明,本文方法能够完全消除因分段导致分段点前后相关性被破坏带来的误差,而且并行化能够提高压缩的效率。

1 相关工作 1.1 轨迹压缩算法简介

轨迹压缩从几十年前开始就有研究,轨迹压缩方法从技术上主要分为三类:第一类是线段简化压缩方法,第二类是基于路网结构的压缩[9-10],第三类是基于语义的压缩[11-12],其中较为经典的还是线段简化压缩。滑动窗口轨迹压缩算法[13-15]和开放窗口轨迹压缩算法[16]就是基于线段简化压缩方法中较为经典的两种轨迹压缩方法。

滑动窗口轨迹压缩算法是目前公认的经典轨迹处理算法[13-14],它不需要明确轨迹数据的终止轨迹点,适用于很多实际的应用中。滑动窗口轨迹压缩算法的主要思想就是从轨迹起点开始,初始化一个大小为1的滑动窗口,并逐步增大窗口的大小,从而逐步加入后续的轨迹点,把窗口的第一个轨迹点和最后一个轨迹点进行连接,得到的线段作为近似线段,然后计算近似线段与原始轨迹的垂直欧氏距离,若距离小于设定的阈值,则继续增大滑动窗口的大小,直到窗口内的误差小于设定的距离阈值。滑动窗口轨迹压缩算法只考虑当前窗口内轨迹点的位置,因此在每个局部能做到最优。文献[17]提出了一种改进的滑动窗口轨迹数据压缩算法,将滑动窗口最大偏移距离参考轨迹点作为当前待压缩轨迹点能否被压缩的判据,从而显著降低算法的时间复杂度,减少压缩处理的时间。

开放窗口轨迹压缩算法与滑动窗口轨迹压缩算法类似,设定一个窗口,在窗口内进行数据压缩,与滑动窗口不同的是,开放窗口轨迹压缩算法计算窗口内每一个点的垂直欧氏距离和时间同步欧氏距离,可以选取窗口内误差总和大于阈值时,窗口内倒数第二个轨迹点作为该窗口内近似线段的终点,也可以选取窗口内贡献最大距离的轨迹点作为该窗口的近似线段的终点。

1.2 MapReduce简介

MapReduce并行计算架构是一个并行计算程序执行系统。它提供了一个包含Map和Reduce两个阶段的并行处理模型和过程,提供一个并行化编程模型和接口,采用了对数据“分而治之”的方法来完成并行化的大数据处理。MapReduce以键值对数据输入方式来处理数据,并能自动完成数据的划分和调度管理。

MapReduce定义了如下的Map和Reduce两个抽象编程接口,由用户去编程实现:

$ {\rm{Map}}:(key,value) - > [(key',value')] $

其中,输入参数是键值对 (keyvalue) 表示的数据。相应的处理逻辑是:一个数据记录将以“键值对”形式传入Map函数;Map函数将处理这些键值对,并以另一种键值对形式输出一组键值对表示的中间结果[(key′,value′)]。

$ {\rm{Reduce}}:(key',[value']) - > [(key'',value'')] $

其中:输入参数是由Map函数输出的一组中间结果键值对 (key′,[value′]),[value′]是一个值的集合,是因为同一个主键key′下通常会包含多个不同的结果值value′,所以传入Reduce函数时会将具有相同主键key′下的所有值value′合并到一个集合中处理。相应的处理逻辑是:对Map输出的这组中间结果键值对,将进一步进行某种整理计算,最终输出为某种形式的结果键值对[(key″,value″)]。

1.3 轨迹处理相关的并行算法

由于Hadoop MapReduce在处理大数据上的优越性,因此文献[18]中对大规模车辆GPS轨迹数据进行地图匹配时,采用了MapReduce的编程思想,将匹配任务分配给各个节点进行处理,匹配时间明显小于集中式的匹配时间。文献[19]中通过MapReduce编程模型,对公共汽车GPS轨迹数据进行校正,在获得公共汽车准确的投影点和计算其运行方向上明显缩短了处理的时间。文献[20]通过MapReduce并行化思想,对大规模时空数据的聚类,由于对时空轨迹数据挖掘不适用于TB或者PB级别的数据量,因此,作者提出基于MapReduce的并行化轨迹聚类策略,并且实验结果显示随着数据规模的增大,并行化轨迹聚类实验运行效率明显高于串行化轨迹聚类。

虽然对于轨迹压缩算法有比较多的改进方法,而且MapReduce并行化计算对处理大量的轨迹数据具有优越性,但是对于并行化轨迹压缩算法尚未见全面报道。本文提出了基于MapReduce的并行化轨迹压缩方法,虽然轨迹压缩并行化会导致分段点前后轨迹的相关性被破坏,但是,用两种划分方法划分轨迹,并对其并行化压缩之后的压缩结果进行匹配合并,能够完全消除因分段导致分段点前后相关性被破坏带来的误差,而且并行化能够提高压缩的效率。

2 基于MapReduce的轨迹压缩算法描述 2.1 轨迹压缩算法并行化策略

在对轨迹压缩进行实验时发现,当实验数据增加到500 MB (轨迹点个数约为780万) 时,压缩时间就超过4 h,当轨迹数据增大到TB、PB级别时,这将给数据的压缩带来极大的困难。针对这一问题,本文提出一种并行化轨迹压缩方法,该方法把轨迹压缩的任务分给多个节点进行压缩,每个节点只需要压缩存储在本地的轨迹数据即可,极大地提高了压缩的效率。同时,又因为并行化会破坏分段点前后轨迹点的相关性,因此需要对原始轨迹点进行两种不同划分,并且第二种划分的分段点要错开第一种划分的分段点。将划分后的轨迹段分到不同的节点上压缩,然后将压缩结果分到不同节点上进行匹配合并,以此来消除因分段产生的误差,同时并行化压缩还能够提高压缩效率,而且经实验证明该策略也适用于与滑动窗口轨迹压缩算法相类似的其他轨迹压缩算法,如开放窗口轨迹压缩算法。

下面举例说明并行化轨迹压缩方法的基本思路:假设存在待压缩轨迹序列T={P0P1P2P3P4P5P6P7P8P9P10P11P12P13P14},假设对T进行集中式轨迹压缩且压缩结果为T′={P0P3P6P8P11P14}。将轨迹序列T按照两种方式分段,如图 1(a)所示。用第一种方式分为3段, 分别标记为〈1, 1〉、〈1, 2〉、〈1, 3〉;用第二种方式分为2段, 标记为〈2, 1〉、〈2, 2〉。由于分段会导致分段点前后轨迹的相关性被破坏使得压缩后产生误差,因此第二种方式的目的主要是错开第一种划分方法的分段点,用于下一步匹配合并来减少这种误差;将所有的轨迹分段记录作为Map函数的输入,不同分段分配到不同节点上进行并行压缩,即将轨迹段〈1, 1〉、〈1, 2〉、〈1, 3〉、〈2, 1〉、〈2, 2〉分别放到不同节点上调用集中式轨迹压缩算法进行压缩。每一个Map函数对每一段轨迹序列进行压缩处理并输出作为Reduce函数的输入,根据key值的不同将Map过程并行化压缩后的轨迹划分到不同的Reduce节点上处理,即〈1, 1〉、〈1, 2〉、〈2, 1〉轨迹序列压缩结果放到Reduce1上进行匹配合并,〈1, 2〉、〈1, 3〉、〈2, 2〉轨迹序列压缩结果放到Reduce2上进行匹配合并,如图 1(b)所示。合并步骤如下:分别将分段方式为1和2的分段压缩结果按照轨迹的先后顺序重新组成轨迹序列S1S2,对于每一个Reduce节点来讲,截取位于S2轨迹序列上从PrbPre之间的轨迹子序列替换到位于S1上从PrbPre之间的轨迹子序列 (Prb为位于分段轨迹点P4之前且距P4最近的S1S2上的共同点P3Pre为位于距分段点P5之后且距P5最近的S1S2上的共同点P6)。由于Reduce1和Reduce2上都有轨迹段〈1, 2〉,因此输出结果时需要去重操作,则最终输出轨迹序列S1′={P0P3P6P8P11P14},如图 1(c)所示。比较图 1(b)图 1(c),同时与集中式压缩结果T′相比较可以看出,轨迹序列S1上有4个点是因分段产生的误差点P4P5P9P10,经过匹配合并被去除掉了。

图 1 并行化轨迹压缩算法过程示例图 Figure 1 Schematic diagram of parallel trajectory compression algorithm

根据上述描述,基于MapReduce的并行化轨迹压缩方法流程如图 2所示。首先将预处理后的轨迹划分到不同的Map节点上,每个节点分别调用集中式轨迹压缩算法对存储在本地的GPS轨迹进行压缩,生成中间键值对〈key, value〉,key是分段序号k经过处理后得到的,value是经过集中式轨迹压缩算法压缩后的轨迹三元组;Shuffle是Map和Reduce之间的过程,是描述数据从Map端传输到Reduce端的过程,该过程会根据key对Map产生的中间键值对进行“分区”,划分到不同Reduce上;Reduce过程则是对轨迹点进行匹配合并,并输出最终合并后的结果。

图 2 并行化轨迹压缩算法流程 Figure 2 Flow chart of parallel trajectory compression algorithm
2.2 轨迹压缩并行化算法设计 2.2.1 轨迹数据预处理

由于轨迹压缩算法要按照轨迹的先后顺序进行压缩,所以在进行并行化轨迹压缩之前要对待压缩原始轨迹数据进行预处理。

定义GPS轨迹序列T={Pi},其中,Pi为第i个轨迹点,i按照轨迹的时间顺序递增 (i=1, 2, …, n),n为轨迹点总数。将轨迹序列T分段,以三元组形式表示出所有三元组轨迹分段记录〈labelkTk〉,其中,label表示分段的方式,k表示分段的序号,Tk表示第k段的轨迹序列。令Tk={Pj| j∈[bkek]},采用两种方式将轨迹序列分段:

1) 第1种方式将轨迹序列T分成N段,label=1,划分规则如下:

$ {b_k} = 1 + (k - 1)\left\lfloor {n/N} \right\rfloor ,k \in [1,N] $ (1)
$ {e_k} = \left\{ {\begin{array}{*{20}{l}} {k\left\lfloor {n/N} \right\rfloor ,}&{k < N}\\ {n,}&{k = N} \end{array}} \right.;k \in [1,N] $ (2)

2) 第2种方式将轨迹序列T分成N-1段,label=2,划分规则如下:

$ {b_k} = a + (k - 1)(1 + \left\lfloor {n/N} \right\rfloor );k \in [1,N - 1] $ (3)
$ {e_k} = a + (k - 1) + k\left\lfloor {n/N} \right\rfloor ;k \in [1,N - 1] $ (4)

其中:

$ a = \left\lfloor {\left( {1 + \left\lfloor {n/N} \right\rfloor } \right)/2} \right\rfloor $ (5)
2.2.2 Map函数的设计

Map函数的任务是完成对轨迹的压缩,其输入为已经经过预处理的存储在自己本地待压缩三元组轨迹分段记录,Map函数输入数据记录〈keyvalue〉对的形式为〈(labelk),Tk〉。每个Map读取每一段轨迹序列之后,就对该轨迹数据进行压缩,输出中间结果〈key′,value′〉对,其形式为〈中间键,经过Map处理之后生成的三元组轨迹记录〉。Map函数的伪代码如算法1所示:

算法1    在Map过程中进行并行化轨迹压缩。

Function Map (){

输入:key:〈label, k〉; valueTk

输出:key′:经Map处理之后产生的中间键; value′:经过Map处理之后生成的三元组轨迹记录〈label, k, Tk′〉

/*调用集中式轨迹压缩方法压缩轨迹集合Tk*/

Tk′=Centralized_Trajectory_Compress (Tk)

IF key.label == 1 THEN

IF key.k! =1‖key.k! =N THEN

/*如果该分段不是第1种分段方式压缩结果轨迹序列上的第1段和最后1段,那么就复制1份该压缩结果,并将k值减1*/

        context.write (key.k-1, 〈label, k, Tk′〉);

    END IF

END IF

IF key.k! = N Then

    context.write (key.k, 〈label, k, Tk′〉);

ELSE

    context.write (key.k-1, 〈label, k, Tk′〉);

END IF

}

2.2.3 Reduce函数的设计

Reduce函数的任务是分别将标记 (label) 为1和2的分段压缩结果按照时间顺序重新组成轨迹序列S1S2,截取位于轨迹序列S2上的轨迹子序列,并用该轨迹子序列替换S1轨迹序列上分段点附近对应的轨迹子序列,生成最终压缩后的GPS轨迹。Reduce函数的伪代码如算法2所示。

算法2    Reduce过程对两种压缩结果进行匹配合并。

Function Reduce (){

输入:经Map处理之后产生的中间结果键值对; key:经Map处理之后产生的中间键; values:经Map处理后生成的三元组轨迹记录〈label, k, Tk′〉

输出:key′:null; value′:经过并行化轨迹压缩方法压缩并合并后生成的GPS轨迹S1

//合并轨迹序列S1S2

S1= values. Tk′∪values. Tk+1′ for values.label = = 1

S2=values. Tk′ for values.label = = 2

//将位于S2轨迹序列上PrbPre之间的轨迹子序列加入到S1

//轨迹序列上 (参见2.1节)

S1.replace (S2.getSubSegment (Prb, Pre));

//去重并输出匹配合并后的轨迹序列S1′,bkek参见式 (3)~(5)

IF S2.k = = 1 THEN

    S1′=S1.getSubSegment (P0, Pe1);

ELSEIF S2.k = = N-1 THEN

    S1′=S1.getSubSegment (PbN-1, Pn);

ELSE

    S1′=S1.getSubSegment (Pbk, Pek);

END IF

context.write (null, S1′);         //输出最终合并结果S1

}

算法时空复杂度分析:集中式滑动窗口压缩算法的空间复杂度为O(n),时间复杂度为O(n2)。本文提出的基于MapReduce的并行化轨迹压缩方法由于采用了两种方法对轨迹序列进行分段,其空间复杂度为O(2n)。该方法Map阶段的时间复杂度为O(n2/N2),Reduce阶段的时间复杂度为O(3n/N),因此总的时间复杂度为O(n2/N2)。从以上分析可以看出,虽然本文提出的并行化轨迹压缩方法在空间复杂度上略大于集中式的轨迹压缩算法,但是,时间复杂度却比集中式的要小,而且随着N的增大,其优势将愈发明显。

3 测试与性能分析 3.1 实验数据集及实验环境

Hadoop集群包括1台主控节点cMaster和6个计算节点cSlave,每个节点的配置为Inter Core i3-3240, 主频为3.4 GHz,Java环境为JDK1.8,使用的Linux系统版本是Ubuntu14.01,根据Hadoop项目官方网站介绍的方法配置基于Haopp1.2.1版本的集群。

本文采用微软亚洲研究院GeoLife项目组的182名用户在一段时间内收集的数据集,因此实验的轨迹数据集是基于真实的轨迹数据,实验用到的数据集最大为500 MB。

3.2 实验结果及分析

为了验证轨迹压缩并行化之后可以提高轨迹压缩的效率,进行了两组实验,并分别比较了集中式滑动窗口轨迹压缩和并行化滑动窗口轨迹压缩,集中式开放窗口轨迹压缩和并行化开放窗口轨迹压缩在相同大小轨迹数据集下的压缩运行时间,结果如图 3所示,数据集范围在1 MB~ 500 MB (约780万个轨迹点)。从图 3中可以看出,当原始轨迹数据集很小时, 集中式轨迹压缩算法的压缩效率要优于并行化轨迹压缩的效率,这是由于当轨迹数据很小时,并行化的滑动窗口轨迹压缩需要并行化一些初始化过程,因此会用更多的时间。然而随着轨迹数据量的增加,当数据量超过90 MB之后,并行化轨迹压缩所需要的时间就会比集中式的要少,而且随着数据量的增加,集中式轨迹压缩和并行化轨迹压缩所需时间的差值会越来越大。

图 3 集中式轨迹压缩与并行化轨迹压缩运行时间对比 Figure 3 Comparison of running time of centralized and parallel trajectory compressions

为了验证TaskTracker节点数对并行化轨迹压缩算法压缩时间的影响,进行了如下的实验,选取的实验数据大小为500 MB,通过改变TaskTracker节点数,对该数据集进行并行化滑动窗口轨迹压缩 (由于滑动窗口轨迹压缩算法和开放窗口轨迹压缩算法类似,因此只选择其中一种进行实验)。实验结果如图 4所示。从图中可以看出,随着TaskTracker节点数的增加,相同规模的数据进行并行化压缩的时间会越少。

图 4 TaskTracker节点数与轨迹压缩时间关系 Figure 4 Relationship between number of TaskTracker and running time of trajectory compression

同时本文记录并比较了TaskTracker节点数为6,轨迹数据从1 MB增大到500 MB时,Map过程并行化压缩后生成轨迹数据与集中式轨迹压缩生成数据之间的误差占总节点个数的比率,以及经过Reduce过程匹配合并之后误差占总节点个数的比率,如图 5所示。从图 5可以看出,随着轨迹数据增大,误差轨迹点占总节点个数的比率在减少,同时,该误差经过Reduce过程的匹配合并之后都能够完全消除。此实验结果结合图 4实验结果说明,MapReduce并行化适用于处理大量轨迹数据,且能够在保证压缩率的前提下提高处理的效率。因为开放窗口轨迹压缩算法类似于滑动窗口轨迹压缩算法,因此该并行化轨迹压缩算法对那些类似于滑动窗口轨迹压缩算法的轨迹压缩算法具有通用性。

图 5 轨迹数据大小与压缩误差节点个数占总节点个数比率关系 Figure 5 Relationship between size of trajectory data and ratio of number of compression error nodes to total nodes
4 结语

本文提出了一种基于MapReduce框架下的并行化轨迹压缩方法,提高轨迹压缩的计算效率。实验结果表明:轨迹压缩算法在MapReduce并行化后并部署在Hadoop集群上运行,不仅能够提高轨迹压缩的运行效率,而且对类似于滑动窗口轨迹压缩的轨迹压缩算法具有通用性。在当今社会空间轨迹数据爆炸性增长的背景下,在云计算平台上采用高效的MapReduce并行化计算方法实现包括滑动窗口轨迹压缩在内的其他轨迹处理算法具有深远的意义。后期将对压缩后的轨迹采用MapReduce方式求不同用户的轨迹相遇问题,并在此基础上进行基于MapReduce的社区划分等移动模型相关的分析。

参考文献
[1] WEI H, WANG Y, FORMAN G, et al. Fast Viterbi map matching with tunable weight functions[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York:ACM, 2012:613-616.
[2] MIWA T, KIUCHI D, YAMAMOTO T, et al. Development of map matching algorithm for low frequency probe data[J]. Transportation Research Part C:Emerging Technologies, 2012, 22(5): 132-145.
[3] 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 and Geovisualization, 1973, 10(2): 112-122. doi: 10.3138/FM57-6770-U75U-7727
[4] GHEMAWAT S, GOBIOFF H, LEUNG S T. The Google file system[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5): 29-43. doi: 10.1145/1165389
[5] DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113. doi: 10.1145/1327452
[6] YANG H, DASDAN A, HSIAO R L, et al. Map-reduce-merge:simplified relational data processing on large clusters[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2007:1029-1040.
[7] ISARD M, BUDIU M, YU Y, et al. Dryad:distributed data-parallel programs from sequential building blocks[J]. ACM SIGOPS Operating Systems Review, 2007, 41(3): 59-72. doi: 10.1145/1272998
[8] OLSTON C, REED B, SRIVASTAVA U, et al. Pig latin:a not-so-foreign language for data processing[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2008:1099-1110.
[9] KELLARIS G, PELEKIS N, THEODORIDIS Y. Trajectory compression under network constraints[C]//Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases. Berlin:Springer, 2009:392-398.
[10] GOTSMAN R, KANZA Y. Compact representation of GPS trajectories over vectorial road networks[C]//Proceedings of the 13th International Symposium Advances in Spatial and Temporal Databases. Berlin:Springer-Verlag, 2013:241-258.
[11] YAN Z. Towards semantic trajectory data analysis:a conceptual and computational approach[C]//Proceedings of the VLDB 2009 PhD Workshop Co-located with the 35th International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann, 2009:1-6.
[12] SPACCAPIETRA S, PARENT C, DAMIANI M L, et al. A conceptual view on trajectories[J]. Data & Knowledge Engineering, 2008, 65(1): 126-146.
[13] MERATNIA N, BY R A D. Spatiotemporal compression techniques for moving point objects[C]//Proceedings of the 9th International Conference on Extending Database Technology. Berlin:Springer, 2004:765-782.
[14] 张达夫, 张昕明. 基于时空特性的GPS轨迹数据压缩算法[J]. 交通信息与安全, 2013, 31(3): 6-9. ( ZHANG D F, ZHANG X M. GPS trajectory data compression algorithm based on the characteristics of time and space[J]. Traffic Information and Security, 2013, 31(3): 6-9. )
[15] SUN P, XIA S, YUAN G, et al. An overview of moving object trajectory compression algorithms[J]. Mathematical Problems in Engineering, 2016, 2016(3): 1-13.
[16] KEOGH E, CHU S, HART D, et al. An online algorithm for segmenting time series[C]//Proceedings of the 2001 IEEE International Conference on Data Mining. Piscataway, NJ:IEEE, 2001:289-296.
[17] 吴家皋, 刘敏, 韦光, 等. 一种改进的滑动窗口轨迹数据压缩算法[J]. 计算机技术与发展, 2015, 25(12): 47-51. ( WU J G, LIU M, WEI G, et al. An improved trajectory data compression algorithm of sliding window[J]. Computer Technology and Development, 2015, 25(12): 47-51. )
[18] HUANG J, QIAO S, YU H, et al. Parallel map matching on massive vehicle GPS data using MapReduce[C]//Proceedings of the 2013 IEEE 10th International Conference on High Performance Computing and Communications. Piscataway, NJ:IEEE, 2013:1498-1503.
[19] LI D, HAITAO Y, ZHOU X, et al. Map-Reduce for calibrating massive bus trajectory data[C]//Proceedings of the 201313th International Conference on ITS Telecommunications. Piscataway, NJ:IEEE, 2013:44-49.
[20] HU C, KANG X, LUO N, et al. Parallel clustering of big data of spatio-temporal trajectory[C]//Proceedings of the 201511th International Conference on Natural Computation. Piscataway, NJ:IEEE, 2015:769-774.