基于Spark平臺(tái)的大規(guī)模GPS軌跡壓縮方法性能評(píng)估

摘要：城市中大量的公交車、出租車和網(wǎng)約車每天服務(wù)著數(shù)以百萬(wàn)計(jì)的城市居民。這些車輛產(chǎn)生的海量GPS軌跡數(shù)據(jù)給交通大數(shù)據(jù)平臺(tái)帶來(lái)了沉重的存儲(chǔ)成本壓力，GPS軌跡數(shù)據(jù)的壓縮處理迫在眉睫。文章借助大數(shù)據(jù)計(jì)算引擎Spark，以并行化的方式實(shí)現(xiàn)了一組經(jīng)典軌跡壓縮算法，這些算法包括Douglas-Pecuker，Top-Down Time-Ratio，Sliding Window和SQUISH，并在一個(gè)超大規(guī)模真實(shí)數(shù)據(jù)集上驗(yàn)證了該方法。實(shí)驗(yàn)結(jié)果表明該方法表現(xiàn)出很好的性能，31 000輛車?yán)塾?jì)1個(gè)月共117.5 GB的GPS軌跡數(shù)據(jù)，在一個(gè)14節(jié)點(diǎn)組成Spark集群上僅需要438 s即可完成壓縮。

關(guān)鍵詞：GPS軌跡數(shù)據(jù)；軌跡壓縮；Spark

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A

0 引言

包括公共汽車、出租車和網(wǎng)約車在內(nèi)的各種車輛每天都在產(chǎn)生大量的GPS軌跡數(shù)據(jù)。這些數(shù)據(jù)日積月累，需要大量的存儲(chǔ)和計(jì)算資源，給交通大數(shù)據(jù)平臺(tái)的建設(shè)帶來(lái)了前所未有的壓力。因此，需要對(duì)GPS軌跡進(jìn)行壓縮。有部分研究者在Hadoop平臺(tái)使用MapReduce框架對(duì)GPS軌跡數(shù)據(jù)進(jìn)行壓縮，也取得了比較好的壓縮效率^［1-2］。但是由于MapReduce編程模型的天然局限性，軌跡壓縮的效率和可擴(kuò)展性很難得到進(jìn)一步提升。Spark的出現(xiàn)使大規(guī)模GPS軌跡壓縮效率的進(jìn)一步提升成為可能。

本文借助Spark平臺(tái)，利用經(jīng)典的軌跡壓縮算法Douglas-Pecuker（DP）^［3］，Top-Down Time-Ratio（TD-TR）^［4］，Sliding Window（SW）^［5］和SQUISH^［6］進(jìn)行GPS軌跡壓縮，并從算法的壓縮精度、運(yùn)行時(shí)間、平均距離誤差做分析。

1 背景與數(shù)據(jù)集

以深圳市為例，截至2019年12月有1.9萬(wàn)輛公共汽車、3.0萬(wàn)輛出租車、8.0萬(wàn)輛網(wǎng)約車，數(shù)以十萬(wàn)計(jì)的車輛每時(shí)每刻都在產(chǎn)生GPS信號(hào)。假設(shè)每輛車平均30 s產(chǎn)生1條GPS記錄，每條記錄200字節(jié)。每輛車每天、每月、每年分別產(chǎn)生0.288萬(wàn)、8.64萬(wàn)、103.68萬(wàn)條記錄。以上這些車輛每年產(chǎn)生的GPS記錄為1 244.16億條，對(duì)應(yīng)存儲(chǔ)空間為2 488.32 GB，保存這些數(shù)據(jù)需要消耗大量的存儲(chǔ)空間。本次實(shí)驗(yàn)的數(shù)據(jù)是某市31 000輛出租車一個(gè)月的GPS軌跡數(shù)據(jù)，GPS軌跡點(diǎn)11.7億，共117.5 GB。

2 數(shù)據(jù)處理

2.1 數(shù)據(jù)清洗

GPS軌跡數(shù)據(jù)由于設(shè)備精度、信號(hào)不穩(wěn)定等原因，存在各種各樣的數(shù)據(jù)質(zhì)量問(wèn)題，主要包括數(shù)據(jù)異常、重復(fù)記錄等。重復(fù)記錄只是對(duì)于數(shù)據(jù)冗余，而對(duì)結(jié)果沒(méi)有價(jià)值，直接做過(guò)濾操作；而數(shù)據(jù)異常比較少，對(duì)于結(jié)果無(wú)影響，可以直接刪除。

2.2 地圖匹配

本文使用GPS地圖匹配算法^［7］來(lái)校正GPS點(diǎn)序列在電子地圖中的位置，采用一系列算法使車輛GPS點(diǎn)更加精確顯示在電子地圖的路網(wǎng)上。地圖匹配的流程如圖1所示。

地圖匹配所采用的是快速地圖匹配算法（Fast map matching，F(xiàn)MM）^［7］，它是一種將隱馬爾科夫模型與預(yù)計(jì)算相結(jié)合的算法。考慮路網(wǎng)、最短路徑、GPS誤差和拓?fù)浼s束，將GPS軌跡校準(zhǔn)到電子地圖路網(wǎng)上。

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

3.1 壓縮可視化對(duì)比

圖2a顯示了一條未經(jīng)壓縮的軌跡，共1 484個(gè)軌跡點(diǎn)。在4種壓縮算法中，SQUITH算法的壓縮率最高，達(dá)到89%，壓縮之后的軌跡點(diǎn)為161個(gè)（圖2b），經(jīng)過(guò)可視化對(duì)比，發(fā)現(xiàn)肉眼無(wú)法區(qū)分兩種不同壓縮率的不同之處。

3.2 不同數(shù)據(jù)量的壓縮時(shí)間和壓縮率

隨著數(shù)據(jù)量增加，算法執(zhí)行時(shí)間呈上升趨勢(shì)，4種策略的耗時(shí)增長(zhǎng)幅度各不相同如圖3所示。DP算法和TD-TR算法增長(zhǎng)幅度稍大，尤其是在數(shù)據(jù)量大于100 GB時(shí)，SW算法和SQUITH算法稍小。因此，SW算法和SQUITH算法更具有擴(kuò)展性。

4種不同算法在4個(gè)不同規(guī)模數(shù)據(jù)集條件下壓縮的結(jié)果為：SQUITH算法壓縮率最高，平均壓縮率可達(dá)到89%；TD-TR算法壓縮率最低，平均壓縮率為67%。這是因?yàn)闀r(shí)間同步歐式距離（SED）小于垂直歐式距離（PED），在壓縮的過(guò)程中，若采用相同的距離閾值，則同步歐式距離算法所保留的特征點(diǎn)多于垂直歐式距離算法，故TD-TR算法的壓縮率小于DP算法、SW算法。

3.3 閾值與壓縮率和平均誤差

由于SQUITH算法的誤差是無(wú)限制，故只對(duì)其他3種壓縮算法做對(duì)比，通過(guò)設(shè)置不同的閾值距離進(jìn)行壓縮率和平均誤差對(duì)比。如圖4所示，隨著設(shè)定的閾值距離不斷增大，被丟棄的點(diǎn)到相鄰兩特征點(diǎn)的距離也增大，使得平均誤差也隨之增加。

TD-TR算法的壓縮率較低，是因?yàn)椴扇《攘糠绞降脑颍蚀吮Ａ舾嗟奶卣鼽c(diǎn)；同時(shí)，隨著壓縮率的變化，隨著設(shè)定的閾值距離不斷增大，壓縮率也不斷變大。這是因?yàn)楦蟮拈撝稻嚯x使得更少的點(diǎn)保留在軌跡中，同時(shí)軌跡數(shù)據(jù)信息也受到了減弱。

4 結(jié)語(yǔ)

本文利用Spark計(jì)算引擎對(duì)4種經(jīng)典壓縮算法進(jìn)行了并行化的實(shí)現(xiàn)，以多個(gè)評(píng)價(jià)指標(biāo)對(duì)4種不同算法進(jìn)行了系統(tǒng)性的對(duì)比。可以得出：SQUITH的壓縮率在同等條件下最好，壓縮率為89%;DP和SW算法壓縮效果大致相同，壓縮率分別為74%和75%;TD-TR壓縮效果最差，壓縮率為67%。通過(guò)采用控制閾值的方式來(lái)進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)各類算法的平均誤差隨著閾值的增大而增加。117.5 GB的數(shù)據(jù)在一個(gè)14節(jié)點(diǎn)的Spark集群上進(jìn)行壓縮處理只需要438 s。與單節(jié)點(diǎn)壓縮相比，基于Spark平臺(tái)的軌跡壓縮方法可以滿足實(shí)際應(yīng)用的需求。

參考文獻(xiàn)

［1］吳家皋，夏軒，劉林峰.基于MapReduce的軌跡壓縮并行化方法［J］.計(jì)算機(jī)應(yīng)用，2017（5）：1282-1286.

［2］LIANG S Y.Research on the method and application of MapReduce in mobile track big data mining［J］.Recent Advances in Electrical amp; Electronic Engineering，2021（1）：20-28.

［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（2）：112-122.

［4］MERATNIA N，DE BY R A.Spatiotemporal compression techniques for moving point objects［M］//Advances in Database Technology-EDBT 2004.Berlin，Heidelberg：Springer Berlin Heidelberg，2004：765-782.

［5］KEOGH E，CHU S，HART D，et al.An online algorithm for segmenting time series［C］//Proceedings 2001 IEEE International Conference on Data Mining.November 29-December 2，2001.San Jose，CA，USA.IEEE，2002：289-296.

［6］MUCKELL J，HWANG J H，PATIL V，et al.SQUISH：an online approach for GPS trajectory compression［C］//Proceedings of the 2nd International Conference on Computing for Geospatial Research amp; Applications.May 23-25，2011.Washington，D.C.，USA.New York：ACM，2011：1-8.

［7］YANG C，GIDóFALVI G.Fast map matching，an algorithm integrating hidden Markov model with precomputation［J］.International Journal of Geographical Information Science，2018（3）：547-570.

（編輯 姚 鑫編輯）

Performance evaluation for GPS trajectory compression methods in Spark platform

Li" Hao， Xiong" Wen*， Liu" Dage

（College of Information Science and Technology， Yunnan Normal University， Kunming 650500， China）

Abstract：" A large number of buses， taxis and e-hailing vehicles in cities serves millions of residents every day. The massive scale GPS trajectories generated by these vehicles had brought heavy storage cost pressure to the operator. Thus， it is urgent to compress the large scale GPS trajectory data in an efficient way. This paper uses Spark， a big data computing engine， to implement a group of classical trajectory compression algorithms in a parallel way， these algorithms include Douglas-Pecuker， Top-Down Time-Ratio， Sliding Window and SQUISH. Then， we validate these algorithms on a very large GPS trajectories dataset， which contains 117.5 GB GPS trajectory data produced by 31 000 vehicles in one month. The experimental results show that it takes only 438 s to compress the dataset in a Spark cluster with 14 nodes.

Key words： GPS trajectory data; trajectory compression; Spark