基于Spark平臺的大規模GPS軌跡壓縮方法性能評估

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

關鍵詞：GPS軌跡數據；軌跡壓縮；Spark

中圖分類號：TP301 文獻標志碼：A

0 引言

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

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

1 背景與數據集

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

2 數據處理

2.1 數據清洗

GPS軌跡數據由于設備精度、信號不穩定等原因，存在各種各樣的數據質量問題，主要包括數據異常、重復記錄等。重復記錄只是對于數據冗余，而對結果沒有價值，直接做過濾操作；而數據異常比較少，對于結果無影響，可以直接刪除。

2.2 地圖匹配

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

地圖匹配所采用的是快速地圖匹配算法（Fast map matching，FMM）^［7］，它是一種將隱馬爾科夫模型與預計算相結合的算法。考慮路網、最短路徑、GPS誤差和拓撲約束，將GPS軌跡校準到電子地圖路網上。

3 實驗結果分析

3.1 壓縮可視化對比

圖2a顯示了一條未經壓縮的軌跡，共1 484個軌跡點。在4種壓縮算法中，SQUITH算法的壓縮率最高，達到89%，壓縮之后的軌跡點為161個（圖2b），經過可視化對比，發現肉眼無法區分兩種不同壓縮率的不同之處。

3.2 不同數據量的壓縮時間和壓縮率

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

4種不同算法在4個不同規模數據集條件下壓縮的結果為：SQUITH算法壓縮率最高，平均壓縮率可達到89%；TD-TR算法壓縮率最低，平均壓縮率為67%。這是因為時間同步歐式距離（SED）小于垂直歐式距離（PED），在壓縮的過程中，若采用相同的距離閾值，則同步歐式距離算法所保留的特征點多于垂直歐式距離算法，故TD-TR算法的壓縮率小于DP算法、SW算法。

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

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

TD-TR算法的壓縮率較低，是因為采取度量方式的原因，故此保留更多的特征點；同時，隨著壓縮率的變化，隨著設定的閾值距離不斷增大，壓縮率也不斷變大。這是因為更大的閾值距離使得更少的點保留在軌跡中，同時軌跡數據信息也受到了減弱。

4 結語

本文利用Spark計算引擎對4種經典壓縮算法進行了并行化的實現，以多個評價指標對4種不同算法進行了系統性的對比。可以得出：SQUITH的壓縮率在同等條件下最好，壓縮率為89%;DP和SW算法壓縮效果大致相同，壓縮率分別為74%和75%;TD-TR壓縮效果最差，壓縮率為67%。通過采用控制閾值的方式來進行實驗，發現各類算法的平均誤差隨著閾值的增大而增加。117.5 GB的數據在一個14節點的Spark集群上進行壓縮處理只需要438 s。與單節點壓縮相比，基于Spark平臺的軌跡壓縮方法可以滿足實際應用的需求。

參考文獻

［1］吳家皋，夏軒，劉林峰.基于MapReduce的軌跡壓縮并行化方法［J］.計算機應用，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