吳家皋，夏 軒，劉林峰,2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院, 南京 210003; 2.計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)),南京 211189)

基于MapReduce的軌跡壓縮并行化方法

吳家皋1,2*，夏 軒1，劉林峰1,2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院, 南京 210003; 2.計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)),南京 211189)

(*通信作者電子郵箱jgwu@njupt.edu.cn)

帶有全球定位系統(tǒng)(GPS)功能設(shè)備的增多，產(chǎn)生大量的時(shí)空軌跡數(shù)據(jù), 給數(shù)據(jù)的存儲(chǔ)、傳輸和處理帶來(lái)了沉重的負(fù)擔(dān)。為了減輕這種負(fù)擔(dān)，各種軌跡壓縮方法也隨之產(chǎn)生。提出了一種基于MapReduce的并行化軌跡壓縮方法，針對(duì)并行化導(dǎo)致的分段點(diǎn)前后軌跡的相關(guān)性被破壞的問(wèn)題，首先,采用兩種分段點(diǎn)相互交錯(cuò)的劃分方法劃分軌跡;然后,將分段軌跡分配到多個(gè)節(jié)點(diǎn)上進(jìn)行并行化壓縮;最后,對(duì)壓縮結(jié)果進(jìn)行匹配合并。性能測(cè)試分析結(jié)果表明,所提出的并行化軌跡壓縮方法能夠大幅提高壓縮效率，而且能完全消除因分段導(dǎo)致分段點(diǎn)前后相關(guān)性被破壞帶來(lái)的誤差。

軌跡壓縮；分布式存儲(chǔ)；MapReduce；Hadoop；全球定位系統(tǒng)軌跡

0 引言

在許多城市，人們駕駛裝備了全球定位系統(tǒng)(Global Positioning System, GPS)設(shè)備的探測(cè)車(chē)沿著道路行進(jìn)來(lái)收集軌跡數(shù)據(jù)，這些數(shù)據(jù)可以被應(yīng)用在很多領(lǐng)域，例如交通信息服務(wù)、導(dǎo)航服務(wù)、公交車(chē)到達(dá)時(shí)間服務(wù)等[1-2]。GPS軌跡數(shù)據(jù)包含著海量的數(shù)據(jù)信息。據(jù)統(tǒng)計(jì)，假設(shè)GPS每隔5 s采集一次信息，那么1輛車(chē)一天就需要大概70 MB的存儲(chǔ)空間，而一個(gè)城市所有車(chē)輛需要的存儲(chǔ)空間將非常龐大，對(duì)如此龐大數(shù)據(jù)的查詢(xún)、分析和傳輸是極具挑戰(zhàn)性的，因此對(duì)GPS軌跡數(shù)據(jù)壓縮的研究成為這一領(lǐng)域的熱點(diǎn)。

在對(duì)移動(dòng)軌跡進(jìn)行存儲(chǔ)時(shí)，其實(shí)只需要存儲(chǔ)能夠準(zhǔn)確描述移動(dòng)軌跡信息的點(diǎn)，其他的軌跡點(diǎn)可以作為冗余軌跡點(diǎn)舍棄掉。而軌跡壓縮的目的就是在保留數(shù)據(jù)包含的信息的前提下，盡可能地減少數(shù)據(jù)量，也就是說(shuō)當(dāng)輸入一條軌跡，通過(guò)軌跡壓縮方法[3]可以輸出一條占用更少空間的壓縮軌跡，而壓縮軌跡與原始軌跡之間的誤差必須是在可以接受的范圍內(nèi)。

隨著軌跡數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)，集中式軌跡壓縮方法將會(huì)受到性能瓶頸制約，因此，迫切需要一種技術(shù)來(lái)解決龐大的軌跡數(shù)據(jù)帶來(lái)的難題。面對(duì)這種難題，云計(jì)算提供了可觀的前景來(lái)應(yīng)對(duì)這些急劇增長(zhǎng)的數(shù)據(jù)量; 同時(shí)，目前對(duì)于大規(guī)模的分布式存儲(chǔ)和云計(jì)算的研究也比較多，例如: 谷歌文件系統(tǒng)(Google File System, GFS)[4]、MapReduce[5]、Map-reduce-merge[6]、Dryad[7]、Pig latin[8]等。最近，尤其是GFS和Map-Reduce架構(gòu)在大數(shù)據(jù)分析方面性能相對(duì)優(yōu)越，因此在世界范圍內(nèi)引起了越來(lái)越多的關(guān)注。Hadoop MapReduce為大數(shù)據(jù)處理提供了一個(gè)很好的平臺(tái)，它主要運(yùn)用的是“分而治之”的思想，目的就是將任務(wù)分給好多個(gè)節(jié)點(diǎn)去處理，提高處理效率，因此，可以將原始軌跡分段分給多個(gè)節(jié)點(diǎn)進(jìn)行壓縮處理，但是將軌跡壓縮任務(wù)并行化卻會(huì)導(dǎo)致分段點(diǎn)前后軌跡的相關(guān)性被破壞。

針對(duì)上述問(wèn)題，本文研究提出了一種基于MapReduce的并行化軌跡壓縮方法。該方法首先將一條軌跡數(shù)據(jù)按照兩種方式分段，并且使得這兩種分段方式的分段點(diǎn)相互錯(cuò)開(kāi)；其次將每一段劃分到不同節(jié)點(diǎn)上并行壓縮；最后將兩種劃分的軌跡數(shù)據(jù)壓縮結(jié)果相互匹配合并，以此來(lái)消除因分段帶來(lái)的誤差。實(shí)驗(yàn)結(jié)果表明，本文方法能夠完全消除因分段導(dǎo)致分段點(diǎn)前后相關(guān)性被破壞帶來(lái)的誤差，而且并行化能夠提高壓縮的效率。

1 相關(guān)工作

1.1 軌跡壓縮算法簡(jiǎn)介

軌跡壓縮從幾十年前開(kāi)始就有研究，軌跡壓縮方法從技術(shù)上主要分為三類(lèi)：第一類(lèi)是線段簡(jiǎn)化壓縮方法，第二類(lèi)是基于路網(wǎng)結(jié)構(gòu)的壓縮[9-10]，第三類(lèi)是基于語(yǔ)義的壓縮[11-12]，其中較為經(jīng)典的還是線段簡(jiǎn)化壓縮?；瑒?dòng)窗口軌跡壓縮算法[13-15]和開(kāi)放窗口軌跡壓縮算法[16]就是基于線段簡(jiǎn)化壓縮方法中較為經(jīng)典的兩種軌跡壓縮方法。

滑動(dòng)窗口軌跡壓縮算法是目前公認(rèn)的經(jīng)典軌跡處理算法[13-14]，它不需要明確軌跡數(shù)據(jù)的終止軌跡點(diǎn)，適用于很多實(shí)際的應(yīng)用中?；瑒?dòng)窗口軌跡壓縮算法的主要思想就是從軌跡起點(diǎn)開(kāi)始，初始化一個(gè)大小為1的滑動(dòng)窗口，并逐步增大窗口的大小，從而逐步加入后續(xù)的軌跡點(diǎn)，把窗口的第一個(gè)軌跡點(diǎn)和最后一個(gè)軌跡點(diǎn)進(jìn)行連接，得到的線段作為近似線段，然后計(jì)算近似線段與原始軌跡的垂直歐氏距離，若距離小于設(shè)定的閾值，則繼續(xù)增大滑動(dòng)窗口的大小，直到窗口內(nèi)的誤差小于設(shè)定的距離閾值。滑動(dòng)窗口軌跡壓縮算法只考慮當(dāng)前窗口內(nèi)軌跡點(diǎn)的位置，因此在每個(gè)局部能做到最優(yōu)。文獻(xiàn)[17]提出了一種改進(jìn)的滑動(dòng)窗口軌跡數(shù)據(jù)壓縮算法，將滑動(dòng)窗口最大偏移距離參考軌跡點(diǎn)作為當(dāng)前待壓縮軌跡點(diǎn)能否被壓縮的判據(jù)，從而顯著降低算法的時(shí)間復(fù)雜度，減少壓縮處理的時(shí)間。

開(kāi)放窗口軌跡壓縮算法與滑動(dòng)窗口軌跡壓縮算法類(lèi)似，設(shè)定一個(gè)窗口，在窗口內(nèi)進(jìn)行數(shù)據(jù)壓縮，與滑動(dòng)窗口不同的是，開(kāi)放窗口軌跡壓縮算法計(jì)算窗口內(nèi)每一個(gè)點(diǎn)的垂直歐氏距離和時(shí)間同步歐氏距離，可以選取窗口內(nèi)誤差總和大于閾值時(shí)，窗口內(nèi)倒數(shù)第二個(gè)軌跡點(diǎn)作為該窗口內(nèi)近似線段的終點(diǎn)，也可以選取窗口內(nèi)貢獻(xiàn)最大距離的軌跡點(diǎn)作為該窗口的近似線段的終點(diǎn)。

1.2 MapReduce簡(jiǎn)介

MapReduce并行計(jì)算架構(gòu)是一個(gè)并行計(jì)算程序執(zhí)行系統(tǒng)。它提供了一個(gè)包含Map和Reduce兩個(gè)階段的并行處理模型和過(guò)程，提供一個(gè)并行化編程模型和接口，采用了對(duì)數(shù)據(jù)“分而治之”的方法來(lái)完成并行化的大數(shù)據(jù)處理。MapReduce以鍵值對(duì)數(shù)據(jù)輸入方式來(lái)處理數(shù)據(jù)，并能自動(dòng)完成數(shù)據(jù)的劃分和調(diào)度管理。

MapReduce定義了如下的Map和Reduce兩個(gè)抽象編程接口，由用戶(hù)去編程實(shí)現(xiàn)：

Map：(key，value)->[(key′，value′)]

其中，輸入?yún)?shù)是鍵值對(duì)(key，value)表示的數(shù)據(jù)。相應(yīng)的處理邏輯是：一個(gè)數(shù)據(jù)記錄將以“鍵值對(duì)”形式傳入Map函數(shù)；Map函數(shù)將處理這些鍵值對(duì)，并以另一種鍵值對(duì)形式輸出一組鍵值對(duì)表示的中間結(jié)果[(key′，value′)]。

Reduce：(key′，[value′])->[(key″，value″)]

其中:輸入?yún)?shù)是由Map函數(shù)輸出的一組中間結(jié)果鍵值對(duì)(key′，[value′])，[value′]是一個(gè)值的集合，是因?yàn)橥粋€(gè)主鍵key′下通常會(huì)包含多個(gè)不同的結(jié)果值value′，所以傳入Reduce函數(shù)時(shí)會(huì)將具有相同主鍵key′下的所有值value′合并到一個(gè)集合中處理。相應(yīng)的處理邏輯是：對(duì)Map輸出的這組中間結(jié)果鍵值對(duì)，將進(jìn)一步進(jìn)行某種整理計(jì)算，最終輸出為某種形式的結(jié)果鍵值對(duì)[(key″，value″)]。

1.3 軌跡處理相關(guān)的并行算法

由于Hadoop MapReduce在處理大數(shù)據(jù)上的優(yōu)越性，因此文獻(xiàn)[18]中對(duì)大規(guī)模車(chē)輛GPS軌跡數(shù)據(jù)進(jìn)行地圖匹配時(shí)，采用了MapReduce的編程思想，將匹配任務(wù)分配給各個(gè)節(jié)點(diǎn)進(jìn)行處理，匹配時(shí)間明顯小于集中式的匹配時(shí)間。文獻(xiàn)[19]中通過(guò)MapReduce編程模型，對(duì)公共汽車(chē)GPS軌跡數(shù)據(jù)進(jìn)行校正，在獲得公共汽車(chē)準(zhǔn)確的投影點(diǎn)和計(jì)算其運(yùn)行方向上明顯縮短了處理的時(shí)間。文獻(xiàn)[20]通過(guò)MapReduce并行化思想，對(duì)大規(guī)模時(shí)空數(shù)據(jù)的聚類(lèi)，由于對(duì)時(shí)空軌跡數(shù)據(jù)挖掘不適用于TB或者PB級(jí)別的數(shù)據(jù)量，因此，作者提出基于MapReduce的并行化軌跡聚類(lèi)策略，并且實(shí)驗(yàn)結(jié)果顯示隨著數(shù)據(jù)規(guī)模的增大，并行化軌跡聚類(lèi)實(shí)驗(yàn)運(yùn)行效率明顯高于串行化軌跡聚類(lèi)。

雖然對(duì)于軌跡壓縮算法有比較多的改進(jìn)方法，而且MapReduce并行化計(jì)算對(duì)處理大量的軌跡數(shù)據(jù)具有優(yōu)越性，但是對(duì)于并行化軌跡壓縮算法尚未見(jiàn)全面報(bào)道。本文提出了基于MapReduce的并行化軌跡壓縮方法，雖然軌跡壓縮并行化會(huì)導(dǎo)致分段點(diǎn)前后軌跡的相關(guān)性被破壞，但是，用兩種劃分方法劃分軌跡，并對(duì)其并行化壓縮之后的壓縮結(jié)果進(jìn)行匹配合并，能夠完全消除因分段導(dǎo)致分段點(diǎn)前后相關(guān)性被破壞帶來(lái)的誤差，而且并行化能夠提高壓縮的效率。

2 基于MapReduce的軌跡壓縮算法描述

2.1 軌跡壓縮算法并行化策略

在對(duì)軌跡壓縮進(jìn)行實(shí)驗(yàn)時(shí)發(fā)現(xiàn)，當(dāng)實(shí)驗(yàn)數(shù)據(jù)增加到500 MB(軌跡點(diǎn)個(gè)數(shù)約為780萬(wàn))時(shí)，壓縮時(shí)間就超過(guò)4 h，當(dāng)軌跡數(shù)據(jù)增大到TB、PB級(jí)別時(shí)，這將給數(shù)據(jù)的壓縮帶來(lái)極大的困難。針對(duì)這一問(wèn)題，本文提出一種并行化軌跡壓縮方法，該方法把軌跡壓縮的任務(wù)分給多個(gè)節(jié)點(diǎn)進(jìn)行壓縮，每個(gè)節(jié)點(diǎn)只需要壓縮存儲(chǔ)在本地的軌跡數(shù)據(jù)即可，極大地提高了壓縮的效率。同時(shí)，又因?yàn)椴⑿谢瘯?huì)破壞分段點(diǎn)前后軌跡點(diǎn)的相關(guān)性，因此需要對(duì)原始軌跡點(diǎn)進(jìn)行兩種不同劃分，并且第二種劃分的分段點(diǎn)要錯(cuò)開(kāi)第一種劃分的分段點(diǎn)。將劃分后的軌跡段分到不同的節(jié)點(diǎn)上壓縮，然后將壓縮結(jié)果分到不同節(jié)點(diǎn)上進(jìn)行匹配合并，以此來(lái)消除因分段產(chǎn)生的誤差，同時(shí)并行化壓縮還能夠提高壓縮效率，而且經(jīng)實(shí)驗(yàn)證明該策略也適用于與滑動(dòng)窗口軌跡壓縮算法相類(lèi)似的其他軌跡壓縮算法，如開(kāi)放窗口軌跡壓縮算法。

下面舉例說(shuō)明并行化軌跡壓縮方法的基本思路：假設(shè)存在待壓縮軌跡序列T={P0，P1，P2，P3，P4，P5，P6，P7，P8，P9，P10，P11，P12，P13，P14}，假設(shè)對(duì)T進(jìn)行集中式軌跡壓縮且壓縮結(jié)果為T(mén)′={P0，P3，P6，P8，P11，P14}。將軌跡序列T按照兩種方式分段，如圖1(a)所示。用第一種方式分為3段, 分別標(biāo)記為〈1,1〉、〈1,2〉、〈1,3〉；用第二種方式分為2段,標(biāo)記為〈2,1〉、〈2,2〉。由于分段會(huì)導(dǎo)致分段點(diǎn)前后軌跡的相關(guān)性被破壞使得壓縮后產(chǎn)生誤差，因此第二種方式的目的主要是錯(cuò)開(kāi)第一種劃分方法的分段點(diǎn)，用于下一步匹配合并來(lái)減少這種誤差；將所有的軌跡分段記錄作為Map函數(shù)的輸入，不同分段分配到不同節(jié)點(diǎn)上進(jìn)行并行壓縮，即將軌跡段〈1,1〉、〈1,2〉、〈1,3〉、〈2,1〉、〈2,2〉分別放到不同節(jié)點(diǎn)上調(diào)用集中式軌跡壓縮算法進(jìn)行壓縮。每一個(gè)Map函數(shù)對(duì)每一段軌跡序列進(jìn)行壓縮處理并輸出作為Reduce函數(shù)的輸入，根據(jù)key值的不同將Map過(guò)程并行化壓縮后的軌跡劃分到不同的Reduce節(jié)點(diǎn)上處理，即〈1,1〉、〈1,2〉、〈2,1〉軌跡序列壓縮結(jié)果放到Reduce1上進(jìn)行匹配合并，〈1,2〉、〈1,3〉、〈2,2〉軌跡序列壓縮結(jié)果放到Reduce2上進(jìn)行匹配合并，如圖1(b)所示。合并步驟如下：分別將分段方式為1和2的分段壓縮結(jié)果按照軌跡的先后順序重新組成軌跡序列S1和S2，對(duì)于每一個(gè)Reduce節(jié)點(diǎn)來(lái)講，截取位于S2軌跡序列上從Prb到Pre之間的軌跡子序列替換到位于S1上從Prb到Pre之間的軌跡子序列(Prb為位于分段軌跡點(diǎn)P4之前且距P4最近的S1和S2上的共同點(diǎn)P3，Pre為位于距分段點(diǎn)P5之后且距P5最近的S1和S2上的共同點(diǎn)P6)。由于Reduce1和Reduce2上都有軌跡段〈1,2〉，因此輸出結(jié)果時(shí)需要去重操作，則最終輸出軌跡序列S1′={P0，P3，P6，P8，P11，P14}，如圖1(c)所示。比較圖1(b)和圖1(c)，同時(shí)與集中式壓縮結(jié)果T′相比較可以看出，軌跡序列S1上有4個(gè)點(diǎn)是因分段產(chǎn)生的誤差點(diǎn)P4、P5、P9、P10，經(jīng)過(guò)匹配合并被去除掉了。

根據(jù)上述描述，基于MapReduce的并行化軌跡壓縮方法流程如圖2所示。首先將預(yù)處理后的軌跡劃分到不同的Map節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)分別調(diào)用集中式軌跡壓縮算法對(duì)存儲(chǔ)在本地的GPS軌跡進(jìn)行壓縮，生成中間鍵值對(duì)〈key,value〉，key是分段序號(hào)k經(jīng)過(guò)處理后得到的，value是經(jīng)過(guò)集中式軌跡壓縮算法壓縮后的軌跡三元組；Shuffle是Map和Reduce之間的過(guò)程，是描述數(shù)據(jù)從Map端傳輸?shù)絉educe端的過(guò)程，該過(guò)程會(huì)根據(jù)key對(duì)Map產(chǎn)生的中間鍵值對(duì)進(jìn)行“分區(qū)”，劃分到不同Reduce上；Reduce過(guò)程則是對(duì)軌跡點(diǎn)進(jìn)行匹配合并，并輸出最終合并后的結(jié)果。

圖2 并行化軌跡壓縮算法流程Fig. 2 Flow chart of parallel trajectory compression algorithm

2.2 軌跡壓縮并行化算法設(shè)計(jì)

2.2.1 軌跡數(shù)據(jù)預(yù)處理

由于軌跡壓縮算法要按照軌跡的先后順序進(jìn)行壓縮，所以在進(jìn)行并行化軌跡壓縮之前要對(duì)待壓縮原始軌跡數(shù)據(jù)進(jìn)行預(yù)處理。

定義GPS軌跡序列T={Pi}，其中，Pi為第i個(gè)軌跡點(diǎn)，i按照軌跡的時(shí)間順序遞增(i=1,2,…,n)，n為軌跡點(diǎn)總數(shù)。將軌跡序列T分段，以三元組形式表示出所有三元組軌跡分段記錄〈label，k，Tk〉，其中，label表示分段的方式，k表示分段的序號(hào)，Tk表示第k段的軌跡序列。令Tk={Pj|j∈[bk，ek]}，采用兩種方式將軌跡序列分段：

1)第1種方式將軌跡序列T分成N段，label=1，劃分規(guī)則如下：

bk=1+(k-1)?n/N」;k∈[1,N]

(1)

(2)

2)第2種方式將軌跡序列T分成N-1段，label=2，劃分規(guī)則如下：

bk=a+(k-1)(1+?n/N」);k∈[1,N-1]

(3)

ek=a+(k-1)+k?n/N」;k∈[1,N-1]

(4)

其中：

a=?(1+?n/N」)/2」

(5)

2.2.2 Map函數(shù)的設(shè)計(jì)

Map函數(shù)的任務(wù)是完成對(duì)軌跡的壓縮，其輸入為已經(jīng)經(jīng)過(guò)預(yù)處理的存儲(chǔ)在自己本地待壓縮三元組軌跡分段記錄，Map函數(shù)輸入數(shù)據(jù)記錄〈key，value〉對(duì)的形式為〈(label，k)，Tk〉。每個(gè)Map讀取每一段軌跡序列之后，就對(duì)該軌跡數(shù)據(jù)進(jìn)行壓縮，輸出中間結(jié)果〈key′，value′〉對(duì)，其形式為〈中間鍵，經(jīng)過(guò)Map處理之后生成的三元組軌跡記錄〉。Map函數(shù)的偽代碼如算法1所示：

算法1 在Map過(guò)程中進(jìn)行并行化軌跡壓縮。

Function Map(){ 輸入：key：〈label,k〉;value：Tk輸出：key′：經(jīng)Map處理之后產(chǎn)生的中間鍵;value′：經(jīng)過(guò)Map處理之后生成的三元組軌跡記錄〈label,k,Tk′〉

/*調(diào)用集中式軌跡壓縮方法壓縮軌跡集合Tk*/

Tk′=Centralized_Trajectory_Compress(Tk)

IFkey.label== 1 THEN

IFkey.k!=1‖key.k!=NTHEN

/*如果該分段不是第1種分段方式壓縮結(jié)果軌跡序列上的第1段和最后1段，那么就復(fù)制1份該壓縮結(jié)果，并將k值減1*/ context.write(key.k-1, 〈label,k,Tk′〉); END IF

END IF

IFkey.k!=NThen

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

ELSE

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

END IF

}

2.2.3 Reduce函數(shù)的設(shè)計(jì)

Reduce函數(shù)的任務(wù)是分別將標(biāo)記(label)為1和2的分段壓縮結(jié)果按照時(shí)間順序重新組成軌跡序列S1、S2，截取位于軌跡序列S2上的軌跡子序列，并用該軌跡子序列替換S1軌跡序列上分段點(diǎn)附近對(duì)應(yīng)的軌跡子序列，生成最終壓縮后的GPS軌跡。 Reduce函數(shù)的偽代碼如算法2所示。

算法2 Reduce過(guò)程對(duì)兩種壓縮結(jié)果進(jìn)行匹配合并。

Function Reduce(){ 輸入：經(jīng)Map處理之后產(chǎn)生的中間結(jié)果鍵值對(duì);key：經(jīng)Map處理之后產(chǎn)生的中間鍵;values：經(jīng)Map處理后生成的三元組軌跡記錄〈label,k,Tk′〉

輸出：key′：null;value′：經(jīng)過(guò)并行化軌跡壓縮方法壓縮并合并后生成的GPS軌跡S1′

//合并軌跡序列S1、S2

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

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

//將位于S2軌跡序列上Prb到Pre之間的軌跡子序列加入到S1

//軌跡序列上(參見(jiàn)2.1節(jié))

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

//去重并輸出匹配合并后的軌跡序列S1′，bk、ek參見(jiàn)式(3)～(5)

IFS2.k== 1 THEN

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

ELSEIFS2.k==N-1 THEN

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

ELSE

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

END IF

context.write(null,S1′);

//輸出最終合并結(jié)果S1′

}

算法時(shí)空復(fù)雜度分析：集中式滑動(dòng)窗口壓縮算法的空間復(fù)雜度為O(n)，時(shí)間復(fù)雜度為O(n2)。本文提出的基于MapReduce的并行化軌跡壓縮方法由于采用了兩種方法對(duì)軌跡序列進(jìn)行分段，其空間復(fù)雜度為O(2n)。該方法Map階段的時(shí)間復(fù)雜度為O(n2/N2)，Reduce階段的時(shí)間復(fù)雜度為O(3n/N)，因此總的時(shí)間復(fù)雜度為O(n2/N2)。從以上分析可以看出，雖然本文提出的并行化軌跡壓縮方法在空間復(fù)雜度上略大于集中式的軌跡壓縮算法，但是，時(shí)間復(fù)雜度卻比集中式的要小，而且隨著N的增大，其優(yōu)勢(shì)將愈發(fā)明顯。

3 測(cè)試與性能分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

Hadoop集群包括1臺(tái)主控節(jié)點(diǎn)cMaster和6個(gè)計(jì)算節(jié)點(diǎn)cSlave，每個(gè)節(jié)點(diǎn)的配置為Inter Core i3-3240,主頻為3.4 GHz，Java環(huán)境為JDK1.8，使用的Linux系統(tǒng)版本是Ubuntu14.01，根據(jù)Hadoop項(xiàng)目官方網(wǎng)站介紹的方法配置基于Haopp1.2.1版本的集群。

本文采用微軟亞洲研究院GeoLife項(xiàng)目組的182名用戶(hù)在一段時(shí)間內(nèi)收集的數(shù)據(jù)集，因此實(shí)驗(yàn)的軌跡數(shù)據(jù)集是基于真實(shí)的軌跡數(shù)據(jù)，實(shí)驗(yàn)用到的數(shù)據(jù)集最大為500 MB。

3.2 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證軌跡壓縮并行化之后可以提高軌跡壓縮的效率，進(jìn)行了兩組實(shí)驗(yàn)，并分別比較了集中式滑動(dòng)窗口軌跡壓縮和并行化滑動(dòng)窗口軌跡壓縮，集中式開(kāi)放窗口軌跡壓縮和并行化開(kāi)放窗口軌跡壓縮在相同大小軌跡數(shù)據(jù)集下的壓縮運(yùn)行時(shí)間，結(jié)果如圖3所示，數(shù)據(jù)集范圍在1 MB～ 500 MB(約780萬(wàn)個(gè)軌跡點(diǎn))。從圖3中可以看出，當(dāng)原始軌跡數(shù)據(jù)集很小時(shí),集中式軌跡壓縮算法的壓縮效率要優(yōu)于并行化軌跡壓縮的效率，這是由于當(dāng)軌跡數(shù)據(jù)很小時(shí)，并行化的滑動(dòng)窗口軌跡壓縮需要并行化一些初始化過(guò)程，因此會(huì)用更多的時(shí)間。然而隨著軌跡數(shù)據(jù)量的增加，當(dāng)數(shù)據(jù)量超過(guò)90 MB之后，并行化軌跡壓縮所需要的時(shí)間就會(huì)比集中式的要少，而且隨著數(shù)據(jù)量的增加，集中式軌跡壓縮和并行化軌跡壓縮所需時(shí)間的差值會(huì)越來(lái)越大。

圖3 集中式軌跡壓縮與并行化軌跡壓縮運(yùn)行時(shí)間對(duì)比Fig. 3 Comparison of running time of centralized and parallel trajectory compressions

為了驗(yàn)證TaskTracker節(jié)點(diǎn)數(shù)對(duì)并行化軌跡壓縮算法壓縮時(shí)間的影響，進(jìn)行了如下的實(shí)驗(yàn)，選取的實(shí)驗(yàn)數(shù)據(jù)大小為500 MB，通過(guò)改變TaskTracker節(jié)點(diǎn)數(shù)，對(duì)該數(shù)據(jù)集進(jìn)行并行化滑動(dòng)窗口軌跡壓縮(由于滑動(dòng)窗口軌跡壓縮算法和開(kāi)放窗口軌跡壓縮算法類(lèi)似，因此只選擇其中一種進(jìn)行實(shí)驗(yàn))。實(shí)驗(yàn)結(jié)果如圖4所示。從圖中可以看出，隨著TaskTracker節(jié)點(diǎn)數(shù)的增加，相同規(guī)模的數(shù)據(jù)進(jìn)行并行化壓縮的時(shí)間會(huì)越少。

同時(shí)本文記錄并比較了TaskTracker節(jié)點(diǎn)數(shù)為6，軌跡數(shù)據(jù)從1 MB增大到500 MB時(shí)，Map過(guò)程并行化壓縮后生成軌跡數(shù)據(jù)與集中式軌跡壓縮生成數(shù)據(jù)之間的誤差占總節(jié)點(diǎn)個(gè)數(shù)的比率，以及經(jīng)過(guò)Reduce過(guò)程匹配合并之后誤差占總節(jié)點(diǎn)個(gè)數(shù)的比率，如圖5所示。從圖5可以看出，隨著軌跡數(shù)據(jù)增大，誤差軌跡點(diǎn)占總節(jié)點(diǎn)個(gè)數(shù)的比率在減少，同時(shí)，該誤差經(jīng)過(guò)Reduce過(guò)程的匹配合并之后都能夠完全消除。此實(shí)驗(yàn)結(jié)果結(jié)合圖4實(shí)驗(yàn)結(jié)果說(shuō)明，MapReduce并行化適用于處理大量軌跡數(shù)據(jù)，且能夠在保證壓縮率的前提下提高處理的效率。因?yàn)殚_(kāi)放窗口軌跡壓縮算法類(lèi)似于滑動(dòng)窗口軌跡壓縮算法，因此該并行化軌跡壓縮算法對(duì)那些類(lèi)似于滑動(dòng)窗口軌跡壓縮算法的軌跡壓縮算法具有通用性。

圖4 TaskTracker節(jié)點(diǎn)數(shù)與軌跡壓縮時(shí)間關(guān)系Fig. 4 Relationship between number of TaskTracker and running time of trajectory compression

圖5 軌跡數(shù)據(jù)大小與壓縮誤差節(jié)點(diǎn)個(gè)數(shù)占總節(jié)點(diǎn)個(gè)數(shù)比率關(guān)系Fig. 5 Relationship between size of trajectory data and ratio of number of compression error nodes to total nodes

4 結(jié)語(yǔ)

本文提出了一種基于MapReduce框架下的并行化軌跡壓縮方法，提高軌跡壓縮的計(jì)算效率。實(shí)驗(yàn)結(jié)果表明：軌跡壓縮算法在MapReduce并行化后并部署在Hadoop集群上運(yùn)行，不僅能夠提高軌跡壓縮的運(yùn)行效率，而且對(duì)類(lèi)似于滑動(dòng)窗口軌跡壓縮的軌跡壓縮算法具有通用性。在當(dāng)今社會(huì)空間軌跡數(shù)據(jù)爆炸性增長(zhǎng)的背景下，在云計(jì)算平臺(tái)上采用高效的MapReduce并行化計(jì)算方法實(shí)現(xiàn)包括滑動(dòng)窗口軌跡壓縮在內(nèi)的其他軌跡處理算法具有深遠(yuǎn)的意義。后期將對(duì)壓縮后的軌跡采用MapReduce方式求不同用戶(hù)的軌跡相遇問(wèn)題，并在此基礎(chǔ)上進(jìn)行基于MapReduce的社區(qū)劃分等移動(dòng)模型相關(guān)的分析。

References)

[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.

[4] GHEMAWAT S, GOBIOFF H, LEUNG S T. The Google file system[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5): 29-43.

[5] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[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.

[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] 張達(dá)夫, 張昕明. 基于時(shí)空特性的GPS軌跡數(shù)據(jù)壓縮算法[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ìn)的滑動(dòng)窗口軌跡數(shù)據(jù)壓縮算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 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 2013 13th 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 2015 11th International Conference on Natural Computation. Piscataway, NJ: IEEE, 2015: 769-774.

This work is partially supported by the National Natural Science Foundation of China (61373139，41571389，71301081), the Open Research Fund from Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, China (K93-9-2014-05B), the Scientific Research Foundation of Nanjing University of Posts and Telecommunications (NY214063).

WU Jiagao, born in 1969, Ph. D., associate professor. His research interests include mobile network, cloud computing.

XIA Xuan, born in 1989, M. S. candidate. His research interests include cloud computing, mobility model.

LIU Linfeng, born in 1980, Ph. D., associate professor. His research interests include underwater sensor network.

Parallel trajectory compression method based on MapReduce

WU Jiagao1,2*, XIA Xuan1, LIU Linfeng1,2

(1.SchoolofComputer,NanjingUniversityofPostsandTelecommunications,NanjingJiangsu210003,China;2.KeyLaboratoryofComputerNetworkandInformationIntegrationofMinistryofEducation(SoutheastUniversity),NanjingJiangsu211189,China)

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.

trajectory compression; distributed storage; MapReduce; Hadoop; Global Positioning System (GPS) trajectory

2016-11-07;

2016-12-14。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61373139，41571389，71301081)；東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目(K93-9-2014-05B)；南京郵電大學(xué)科研基金資助項(xiàng)目(NY214063)。

吳家皋(1969—)，男，江蘇蘇州人，副教授，博士，CCF會(huì)員，主要研究方向:移動(dòng)網(wǎng)絡(luò)、云計(jì)算； 夏軒(1989—)，男，江蘇宿遷人，碩士研究生，主要研究方向:云計(jì)算、移動(dòng)模型； 劉林峰(1980—)，男，江蘇丹陽(yáng)人，副教授，博士，CCF會(huì)員，主要研究方向:水下傳感器網(wǎng)絡(luò)。

1001-9081(2017)05-1282-05

10.11772/j.issn.1001-9081.2017.05.1282

TP311

A