基于行駛特征的軌跡壓縮技術*

江俊文，張　凱，王曉玲，金澈清

華東師范大學 數據科學與工程研究院，上海 200062

基于行駛特征的軌跡壓縮技術*

江俊文，張凱，王曉玲+，金澈清

華東師范大學 數據科學與工程研究院，上海 200062

軌跡壓縮；行駛特征；自信息量；馬爾可夫序列

1　引言

近年來，隨著移動設備的普及和定位服務的發展，在很多應用中產生了大量的軌跡數據。例如，車載GPS設備連續采樣車輛在不同時間的位置；在微博、街旁、Foursquare等移動社交網絡上，用戶的簽到序列可以看作是該用戶的旅游軌跡；公交卡、地鐵卡的刷卡記錄顯示了人們何時何地上車或下車，組成人們的出行軌跡。

基于位置的服務（location-based services，LBS）需要處理大量的軌跡數據，比如路線規劃、時間預測等。但是海量軌跡數據為基于位置的服務帶來了許多新的挑戰：（1）數據規模快速膨脹，導致數據存儲面臨著巨大壓力；（2）基于海量軌跡數據的查詢和數據分析性能降低；（3）數據的收集和傳輸會帶來誤差和冗余，從而影響服務器的響應速度。

以車輛行駛軌跡為例，上海、北京等地的出租車上裝載的GPS設備，每隔幾分鐘、幾十秒甚至幾秒鐘就會采樣出租車的行駛狀態，并傳送給服務器。司機的行駛路線、行駛習慣直接反應了城市的交通狀況，并且為人們的出行提供依據。

諸多車輛所產生的軌跡數據對存儲和查詢都帶來了巨大的挑戰。以前的軌跡壓縮算法[1-13]主要關注軌跡的空間和時間，卻很少關注車輛的速度和方向信息。盡管已有的方法能夠有效地減小數據量，但是也會損失速度和方向的信息。例如查詢車輛在某一段路程中的速度變化模式，利用已有的壓縮方法壓縮后的軌跡是無法支持的。鑒于此，本文提出了一種新的壓縮方法Mixture Compression（MC），通過訓練樣本得到車輛的行駛特征，然后根據這些特征為每個軌跡點賦予信息量的值，從而篩選軌跡點。

本文的主要貢獻如下：

（1）挖掘軌跡的行駛特征，分析速度變化、方向變化和路網距離的分布規律，使用高斯分布來擬合特征的分布。

（2）把軌跡建模為馬爾可夫序列，根據高斯分布來估計軌跡點出現的概率，從而計算出各軌跡點的信息量。

（3）提出軌跡壓縮算法Mixture Compression，并在真實數據集上進行驗證，表明了新算法的有效性。

本文組織結構如下：第2章回顧了已有的軌跡數據壓縮工作；第3章定義了待解決的問題；第4章具體描述了新的軌跡壓縮算法；第5章展示了基于真實數據集的實驗效果；第6章總結全文，并展望了未來的工作方向。

2　相關工作

首先回顧已有的軌跡壓縮技術，然后再介紹信息論的相關概念。

2.1軌跡壓縮

現有的軌跡壓縮工作主要有兩方面：一是線段簡化方法；二是基于路網的壓縮方法。

2.1.1線段簡化技術

線段簡化的主要思想是通過設定一個誤差閾值，來削減軌跡中GPS點的數目。這類技術都是基于歐氏空間的，誤差用歐氏空間距離來度量。線段簡化方法又分為兩類，離線壓縮和在線壓縮。

（1）離線壓縮。離線壓縮是指線下壓縮歷史軌跡數據。Douglas-Peucker（DP）[1]算法使用若干條線段來近似原始軌跡，并且保證產生最小的誤差。誤差度量是垂直歐氏距離。整個算法的時間復雜度為O(N2)，N為原始軌跡中點的數目。文獻[2]借助外部存儲結構把算法的時間性能提高到O(N×lbN)。DP算法只考慮了空間距離，沒有考慮時間因素，因此在文獻[3]中提出時間比率距離，計算原始軌跡和近似軌跡中擁有相同時間戳的兩個點的歐氏距離，并把它應用在TD-TR（top-down time-ratio）算法中，獲得了更精確的近似軌跡。算法的時間復雜度仍然為O(N2)。

（2）在線壓縮。離線壓縮能夠獲得更好的近似軌跡，因為它把整條軌跡都考慮在內，但是這類方法的時間復雜度都較高。因此許多新的技術考慮到在線壓縮方法。文獻[4]提出了Sliding Window和Open Window兩種在線壓縮方法。這類方法主要思想是初始化一個大小為1的窗口，并逐步增加窗口的大小，把后續的GPS點包含在內，并用一條直線段來近似窗口內的軌跡，如果誤差大于預先設定的誤差閾值，那么把引起最大誤差的點或者該點的前一個點加入近似軌跡，并以這個點作為下一個窗口的起點。在文獻[5]中，Thresholds算法借助速度和方向，構建了一個扇環形的安全區域，如果接下來的一個點落在安全區域內，就省略這個點，否則就把該點加入近似軌跡。文獻[14]提出SQUISH（spatial quality simplification heuristic）方法，借助優先隊列，逐步加入軌跡點，當隊列溢出時，刪除誤差最小的點。SQUISH-E[15]優化了SQUISH算法的誤差無上界的缺陷，能在給定的誤差閾值內，達到最優的壓縮率。

2.1.2基于路網結構的技術

線段簡化方法是基于歐氏空間的，而車輛的運動要受到路網結構的約束，因此線段簡化方法在車輛軌跡壓縮上有很大的局限性。而基于路網結構的壓縮方法能避免這些問題。文獻[6]提出了Nonmaterial方法，記錄了經過交叉口的時間和順序，來取代原始的GPS點。文獻[7]使用邊來描述軌跡，如果司機從A點到B點行駛的是它們之間的最短路徑，那么只需要保存頭尾兩條邊即可。盡管這種方法可以用更少的邊來代替大量GPS點，但是卻丟失了時間、速度和方向的信息，因此壓縮后的數據僅能支持有限的查詢。文獻[8-9]的目標是找到最優的壓縮路徑，并結合最小描述長度（minimum description length，MDL）的方法，把壓縮問題轉化為目標函數的最優化問題。這種方法無法解決帶環的軌跡，并且如果路網結構很復雜的話，算法的時間復雜度會很高。文獻[10]發現每條路段上的車流量是不均勻的，有些路段車輛經過很頻繁，而有些路段卻很少有車輛經過。因此可以利用這個信息把整條軌跡分解為幾段子軌跡，并根據路段出現的頻率進行哈夫曼編碼，每條軌跡就轉化為編碼的序列，從而顯著減少空間。但是這種方法在使用之前有解壓縮的步驟。文獻[11]和[12]提出了語義壓縮，把一條軌跡轉化為若干個帶語義的事件和地點。這種方法會花費更多的壓縮時間，并且需要解壓才能支持上層應用。文獻[16]從路網結構和軌跡中提取了6個特征，根據這些特征把軌跡切分為子軌跡段，然后用這些特征來描述每段內的行駛狀態。這種提取出的摘要軌跡不僅很好地記錄了軌跡的運行蹤跡，也便于人們理解。

2.2信息論相關概念

信息論常用來研究信息的傳輸、提取和壓縮的問題。本文把軌跡和軌跡點的重要性用信息論中的信息量進行衡量。

車輛在行駛過程中，相鄰的軌跡點有影響關系，也就是說一個軌跡點的狀態是受它前面的軌跡點影響的。統計發現，軌跡點只與它前一個軌跡點的狀態有關，而與更前面的軌跡點無明顯關系，表明軌跡符合馬爾可夫序列的特征，從而可以被建模成馬爾可夫序列。本文利用馬爾可夫序列的特性來解決軌跡壓縮的問題。

假設在馬爾可夫序列中，信號x的出現依賴信號y，因此在y的基礎上x發生的條件概率為Pr(x|y)，此時信號x的條件自信息量為I(x|y)，定義公式如下：

式（1）表示在信號x包含的信息量與x發生的概率成反比。也就是說，在y的基礎上，x發生的概率越小，包含的信息量越高。相反，如果x發生的概率越大，則包含的信息量越低。

條件自信息量用來描述離散隨機變量的信息度量，也可以套用在軌跡點上。下文會具體闡述如何描述軌跡點的信息量。

3　問題定義

其中，T表示任意一條軌跡；|T|表示軌跡的長度；I(pi)表示軌跡點pi的信息量。

綜上所述，本文的問題定義如下：給定一條軌跡T，找到一條壓縮后的軌跡T′，使得T′滿足用戶給定的閾值，盡可能保留原始軌跡的特征，并具有最大的軌跡信息量。

壓縮后的軌跡的信息量由式（3）計算。

本章定義了待解決的問題和相關概念。

定義1（軌跡點）車輛在某時刻的行駛狀態：

其中，time表示采樣時間；latitude、longitude表示車輛所在的緯度和經度；speed表示車輛的速度；direction表示車輛的行駛方向。

定義2（軌跡T）表示車輛的運動蹤跡，用一條軌跡點的序列來表示：

其中，object ID表示車輛的標識號；trajectory ID是軌跡的標識號；pi表示一個軌跡點。

定義3（軌跡點信息量）表示軌跡點的重要性度量。每個軌跡點即是馬爾可夫序列中的一個信號，假設一個軌跡點為 pi，pi受 pi-1的影響，在 pi-1的基礎上，pi的概率為Pr(pi|pi-1)。根據信息論中的信息量概念，定義pi的信息量如下：

規則1一個軌跡點在已知條件下出現的概率越低，則該軌跡點的信息量就越大，該軌跡點更值得保留。

第4章會詳細闡述如何運用規則1計算行駛特征的信息量。

定義4（軌跡信息量）軌跡中所有軌跡點的信息量的總和。計算公式如下：

4　基于行駛特征的壓縮方法

本章介紹一種新的軌跡壓縮方法，從歷史軌跡數據中挖掘司機的行駛特征，分析特征的分布情況。在此基礎上，量化每個軌跡點在各個特征上的信息量和總信息量，選出符合預先設定的閾值的點集合，組成體現軌跡特征的壓縮軌跡。

在車輛軌跡中，用戶感興趣的是車輛的速度、方向和位置信息。GPS設備的采樣頻率不定，若3 s采樣一次，那么一條軌跡包含緊密的軌跡點，因此數據量很大并且包含大量的冗余數據。對軌跡數據進行壓縮時，應盡可能保留體現原始軌跡特征的點，并盡可能減少所帶來的誤差。因此本文對車輛行駛特征，包括速度、方向和位置進行分析，通過這3個維度共同決定軌跡點是否值得保存。

4.1行駛特征的分布

車輛行駛特征是基于2013年10月的某市出租車數據挖掘的。從數據集中隨機采集500條、1 000條和2 000條軌跡，分別來自不同的司機和不同的時間段，如圖1~圖3所示。

4.1.1速度特征

車輛的速度及其變化對研究城市交通狀況很有價值，因此壓縮后的軌跡需要保存具有代表性的速度信息的點。

本文將軌跡建模為馬爾可夫序列，每個軌跡點只與它前一個軌跡點有關，研究相鄰兩個點速度的變化情況。圖1展示了500條、1 000條和2 000條軌跡的分布，可以看出它們都呈現為高斯分布，因而可以用高斯分布來模擬速度變化分布。

4.1.2方向特征

車輛的方向和速度共同決定車輛的位置，并且方向的改變對車輛的運動狀態具有重要的表征作用。而單獨的方向并不能表現車輛行駛的變化，因此壓縮后的軌跡要包含具有代表性的方向信息的軌跡點。

與速度類似，本文研究相鄰點方向的變化情況。圖2展示了500條、1 000條和2 000條軌跡的結果分布，可以看出方向變化也表現出類似高斯分布的特性，并且在0的偏右位置達到峰值。因此也可用高斯分布去模擬方向變化的分布。

Fig.1　Velocity difference statistical figures of 500,1 000 and 2 000 trajectories圖1　軌跡數分別為500、1 000、2 000時速度差值的統計圖

Fig.2　Direction difference statistical figures of 500,1 000 and 2 000 trajectories圖2　軌跡數分別為500、1 000、2 000時方向差值的統計圖

Fig.3　Network distance statistical figures of 500,1 000 and 2 000 trajectories圖3　軌跡數分別為500、1 000、2 000時路網距離差值的統計圖

速度和方向代表車輛的行駛狀態，而根據之前的闡述，速度變化和方向變化都呈現高斯分布，并且在y軸的附近達到峰值。根據高斯分布的特征，知道速度和方向在大概率情況下是變化很小的，而在小概率情況下會變化很大。因此可以假設車輛在運動過程中，速度、方向的變化呈現高斯分布。

4.1.3位置特征

位置信息是軌跡中最重要的數據，幾乎所有的查詢都會涉及到位置信息。因此壓縮后的軌跡必須要盡可能保留準確的時空信息。

在挖掘位置特征之前，首先假設在兩個軌跡點之間，車輛是勻速行駛的，則可把前一個點的瞬時速度當作下一段軌跡的平均速度。車輛所在的位置是由前一個點的速度和方向共同決定的。因此可以通過速度和方向預測下一個點的位置。盡管預測點的位置和實際采樣到的點的位置會存在距離，但是可以對這兩者之間的距離進行建模。

假設在 pi點，已知 pi的速度vi和方向di，根據速度和方向預測到的下一個點的位置為p′i+1，實際的下一個點的位置為 pi+1。計算得到預測點 p′i+1和實際點pi+1之間的路網距離為lpp′。

如果lpp′越小，說明預測得越準確，刪除實際點對軌跡帶來的誤差就越小。如果lpp′越大，說明預測得越不準確，刪除這個點帶來的誤差就越大。

圖3顯示了500條、1 000條和2 000條軌跡的分布情況。可以看出，lpp′的分布呈現高斯分布的特征，因此使用高斯分布去擬合lpp′的分布。

由以上分析可知，車輛的行駛軌跡有3個重要特征，速度、方向和位置。這些特征能充分刻畫軌跡的輪廓，并描述車輛的運動狀態。簡單的速度、方向和位置信息并沒有明顯的分布規律，而軌跡符合馬爾可夫序列的特性，因此軌跡點的速度、方向和位置相對于前一個軌跡點的變化是有規律的。從數據集中發現，速度變化、方向變化和位置變化呈現高斯分布，通過高斯分布擬合這種規律，就可以量化軌跡點的速度、方向和位置出現的概率值。計算公式為：

其中，x表示速度變化、方向變化或位置變化。

4.2行駛特征信息量

下面通過例1來說明信息量的計算過程。

例1如圖4所示，假設有一條軌跡T={p0,p1,p2, p3,p4}，各個軌跡點落在不同的路段上，如黑色實心點所示。其中車輛在p0的速度為v0、方向為d0和經緯度為(x0,y0)，p1點是否保留需要通過考察 p1點的概率和信息量來決定。根據假設1車輛在p0p1以速度v0勻速運動，結合兩點之間的時間信息，可以計算得到在這段時間內車輛行駛的路程，從而預測p1的位置在 p1′（紅色空心點）處，p1′的經緯度位置為(x1′,y1′)。實際采樣到的 p1的經緯度為(x1,y1)。實際點 p1與預測點p1′之間的路網距離為lp1p1′。軌跡點 p1的速度和方向分別為v1和d1。因此p1相對于軌跡點p0的速度變化為v1-v0，方向變化為d1-d0。

Fig.4　Trajectory example圖4軌跡示例

由于速度變化、方向變化和路網距離均符合高斯分布，由式（4）可以計算得到 p1點在p0的基礎上的速度、方向和位置的概率值。

以Iv表示速度維度的信息量，Id表示方向維度的信息量，Il表示位置維度的信息量。根據式（2）和（4）可得：

根據式（5）～（7）計算速度變化、方向變化和位置距離的信息量。事實上如果速度變化、方向變化越小，預測點和實際點位置的路網距離越小，那么概率值越大，則信息量越低。

軌跡點的總信息量由如下公式計算：

即軌跡點的總信息量等于它各個特征的信息量的權重和，其中α+β+γ=1。α、β和γ可以調節3個特征量的權重，權重越大的特征，表明用戶更在意該特征，壓縮后的數據也偏向于該特征，因此這3個值由用戶自定義。在本文的實驗中，為了表示速度、方向和位置特征具有相同的重要性，設置α、β和γ都為1/3。

用戶設置的閾值可以幫助篩選合適的軌跡點。可以利用速度變化的閾值、方向變化的閾值和路網距離的閾值來計算信息量的閾值。但是設定3個閾值帶來的不僅僅是參數增多，更重要的是如何設置3個閾值的大小能控制這3個特征具有相同的影響力，而不會導致篩選出的軌跡點只體現了某一個特征。本文設置一個閾值δ來代替速度變化、方向變化和路網距離的閾值。δ表示在高斯分布中距離期望最遠的兩端的面積。根據高斯分布的面積公式，可以計算得到自變量的范圍，即速度變化、方向變化和路網距離的閾值。LBS服務對軌跡數據的精確性要求是各不相同的，有的服務需要非常精確的軌跡數據，而有些服務可以容忍部分信息的丟失，但要求較快的查詢速度。因此，針對不同的應用，用戶可以設定合適的閾值來篩選出最合適的壓縮軌跡。

4.3基于行駛特征的軌跡壓縮算法

本文提出的行駛特征的軌跡壓縮方法Mixture Compression，根據輸入的參數可以分為兩種：算法1的輸入是原始軌跡ST和用戶自定義閾值δ；算法2的輸入是原始軌跡ST和用戶設定壓縮率cr。

算法1 MC(ST,δ)

輸入：軌跡集合ST，閾值δ∈[0,1]。

輸出：壓縮后的軌跡集合ST′。

1.從軌跡集合中隨機選取2 000條軌跡，訓練得到速度、方向和路網距離的高斯分布參數

2.根據閾值δ和高斯函數計算信息量閾值Iδ

3.初始化數組T′

4.for eachST中軌跡Tdo

5.把T的起點加入到壓縮軌跡T′中

6.for each軌跡點pi(1

7.計算pi在pi-1基礎上的速度差、方向差和距離差

8.計算pi的條件自信息量I(pi)

9.If（I(pi)>Iδ） then

10.把pi加入T′中

11.End for

12.把T的終點加入到壓縮軌跡T′中

13.把T′加入集合ST′中

14.清空T′

15.End for

16.returnST′

首先從軌跡集合中隨機選取2 000條軌跡作為訓練集（第1行），計算得到速度、方向和位置特征的高斯分布函數，訓練步驟是離線處理的，并且計算一次后，可以保存下來并持續使用。值得注意的是，本文實驗采用的是某市出租車軌跡數據集，因此這組訓練參數，只適合該數據集。對于其他類型的數據集，例如公交車的軌跡數據集，需要利用公交車的數據集訓練出適合公交車軌跡的參數。然后，用戶預先設定一個閾值（第2行），結合高斯分布函數，計算得到速度、方向和位置變化的閾值，并最終計算出軌跡點的信息量閾值Iδ。對于每條軌跡T，先把軌跡的起點加入到壓縮軌跡T′中（第4~5行）。從第二個軌跡點開始（第6~11行），計算它與前一個點的速度變化、方向變化和路網距離，根據式（5）~（8）計算該點的信息量I(pi)。如果I(pi)大于Iδ，則保留該點。如果I(pi)小于Iδ，則跳過該軌跡點。接著把T的終點加入T′（第12行）。最終把壓縮后的軌跡T′放入軌跡集合ST′（第13行）。

用戶也可以設定壓縮率來進行壓縮。當給定壓縮率cr時，需要調用算法MCCR（mixture compression of compression rate）。

算法2 MCCR(ST,cr)

輸入：軌跡集合ST，壓縮率cr∈[0,1]。

輸出：壓縮后的軌跡集合ST′。

1.從軌跡集合中隨機選取2 000條軌跡，訓練得到速度、方向和路網距離的高斯分布參數

2.初始化數組T′和temp

3.for eachST中軌跡Tdo

4.把T的起點加入到壓縮軌跡T′中

5.for each軌跡點pi(1

6.計算pi在pi-1基礎上的速度差、方向差和距離差

7.計算pi的條件自信息量I(pi)

8.將二元組加入temp中

9.End for

10.根據I(pi)對temp遞減排序

11.選取temp中前temp.length*cr個軌跡點加入壓縮后的軌跡T′中

12.把T的終點加入到壓縮軌跡T′中

13.把T′加入集合ST′中

14.清空T′和temp

15.End for

16.returnST′

算法2從第3行開始，對每條軌跡的每個軌跡點，計算軌跡點的自信息量，并加入到數組temp中（第5~8行）。對temp依據自信息量進行遞減排序，選取出前temp.length*cr個軌跡點加入T′（第10~12行）。最后把T′加入集合ST′。

5　實驗結果與分析

本文通過實驗來驗證Mixture Compression算法的有效性。基于行駛特征的軌跡壓縮思想在本文中第一次提出，Mixture Compression算法在壓縮數據量的同時，也保證了壓縮后的軌跡具有原始軌跡的特征。為了體現新算法的有效性，選取了兩個Baseline算法進行對比，DP（Douglas-Peucker）算法[1]和Thresholds算法[5]。DP算法和Thresholds算法都屬于線段簡化技術，DP只考慮了距離因素，Thresholds考慮了速度和方向的因素，而Mixture Compression考慮了速度、方向和距離因素。

首先介紹了實驗的數據集和運行環境。其次比較了Mixture Compression算法和Baseline方法的壓縮率。最后比較了Mixture Compression算法和Baseline方法的誤差。

5.1實驗設置

本文采用真實的出租車軌跡數據構建實驗。數據集是2013年10月某市出租車軌跡數據，大小約為2 GB。每一行記錄表示車載GPS采樣到的出租車信息，包含經緯度、速度、方向、載客狀態信息。軌跡的采樣間隔不同，為十幾秒至幾分鐘不等。為了降低軌跡數據的差錯率，首先進行了Map-Matching預處理。

本文的實驗代碼用Java編寫，運行在配置2.0 GHz Intel Xeon處理器、16 GB內存的64位Windows 8操作系統上。為了進行性能對比，本文實現了DP算法[1]和Thresholds[5]算法。DP算法原來工作于歐氏空間內，使用垂直歐氏距離作為距離函數。本文則使用路網距離作為距離函數。Thresholds算法考慮速度和方向信息來構造安全區域，以過濾掉落在安全區域里面的軌跡點。

本文主要從壓縮率和誤差兩方面進行評測。閾值從0.1到1.0逐步增加，比較Mixture Compression 和Baseline算法的壓縮效果。相同閾值情況下，如果壓縮率越小，則說明算法越有效。本文使用速度誤差、方向誤差和距離誤差來衡量壓縮軌跡的誤差。在壓縮率不變時，比較不同算法的誤差。

5.2壓縮率比較

本實驗比較相同閾值下的壓縮率。壓縮率（compression rate，CR）的計算公式如下：

其中，|T′|表示壓縮后的軌跡的長度；|T|表示原始軌跡的長度。顯然，|T′|<|T|。

從圖5可知，隨著閾值的增加，壓縮率也逐漸增加。與兩種Baseline技術相比較，在相同的閾值條件下，Mixture Compression的壓縮率更小。例如當閾值為0.1時，Mixture Compression比Baseline方法的壓縮率好5~6倍，也就是說壓縮后的數據大小是Baseline方法的1/5到1/6。Mixture Compression比Baseline方法的平均壓縮效果要好4倍左右。值得注意的是，在閾值為1.0的條件下，Mixture Compression比Baseline方法要好一些。這是因為出租車在行駛過程中，遇到紅燈或者上下客時會停車，Mixture Compression能壓縮這部分數據。

Fig.5　Compression rate圖5 壓縮率比較

5.3誤差比較

本實驗評測不同壓縮算法的誤差情況。鑒于軌跡需要同時考慮空間、時間、速度和方向等信息，因此使用平均時間同步速度誤差（average time synchronized velocity distance，ATSVD）、平均時間同步方向誤差（average time synchronized direction distance，ATSDD）和平均時間同步的路網距離（average time synchronized network distance，ATSND）作為誤差衡量。時間同步的兩點是指壓縮后的軌跡中與原始軌跡中時間匹配的點。ATSVD是指兩條軌跡中所有時間同步的兩點的速度誤差的平均值。ATSDD是指兩條軌跡中所有時間同步的兩點的方向誤差的平均值。ATSND是指兩條軌跡中所有時間同步的兩點之間的路網距離的平均值。計算公式如下所示：

圖6~圖8展示了基于真實數據集的實驗結果。可以發現隨著壓縮率增大，每種方法的誤差都逐漸減小。這是因為如果壓縮后的數據越大，那么它跟原始軌跡相差就越小，所以平均速度誤差、平均方向誤差和平均路網距離也越小。此外，在各種情況下，Mixture Compression的誤差均低于對比算法，表示Mixture Compression方法更優。比如壓縮率為30%的時候，Mixture Compression的平均速度誤差為4 km/h，平均方向誤差為35°，平均路網誤差只有80 m，均優于DP算法和Thresholds算法，約為它們的1/4到1/2。而當壓縮率達到40%以上，Mixture Compression的誤差是DP或者Thresholds的1/3，甚至是1/10。隨著壓縮率的增大，Mixture Compression在誤差方面的優勢更明顯。

Fig.6　Average velocity error圖6　平均速度誤差比較

Fig.7　Average direction error圖7 平均方向誤差比較

Fig.8　Average network distance error圖8　平均距離誤差比較

6　結束語

本文提出了一種軌跡壓縮技術，綜合考慮了位置、速度、方向等信息。本文方法采用馬爾可夫模型對軌跡建模，繼而從速度變化、方向變化和路網距離維度上考察其分布。最終借助高斯分布來預測軌跡下一個點的狀態，并賦予一個信息量值來表示這個點的重要性。實驗結果表明本文方法在壓縮率和精度上具有優勢，能有效地壓縮軌跡。未來可以研究基于行駛特征的查詢。

References:

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

[2]Hershberger J E,Snoeyink J.Speeding up the Douglas-Peucker line-simplification algorithm[D].University of British Columbia,Department of Computer Science,1992.

[3]Meratnia N,de By R A.Spatiotemporal compression techniques for moving point objects[C]//LNCS 2992:Proceedings of the 9th International Conference on Extending Database Technology,Heraklion,Greece,Mar 14-18,2004. Berlin,Heidelberg:Springer,2004:765-782.

[4]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,San Jose,USA,Nov 29-Dec 2,2001.Piscataway,USA:IEEE,2001:289-296.

[5]Potamias M,Patroumpas K,Sellis T.Sampling trajectory streams with spatiotemporal criteria[C]//Proceedings of the 18th International Conference on Scientific and Statistical Database Management,Vienna,Austria,Jul 3-5,2006.Piscataway,USA:IEEE,2006:275-284.

[6]Lerin P M,Yamamoto D,Takahashi N.Encoding travel traces by using road networks and routing algorithms[M]//Intelligent Interactive Multimedia:Systems and Services.Berlin, Heidelberg:Springer,2012:233-243.

[7]Kellaris G,Pelekis N,Theodoridis Y.Trajectory compression under network constraints[M]//Advances in Spatial and Temporal Databases.Berlin,Heidelberg:Springer,2009: 392-398.

[8]Kellaris G,Pelekis N,Theodoridis Y.Map-matched trajectory compression[J].Journal of Systems and Software,2013,86 (6):1566-1579.

[9]Song Renchu,Sun Weiwei,Zheng Baihua,et al.PRESS:a novel framework of trajectory compression in road networks[J].Proceedings of the VLDB Endowment,2014,7 (9):661-672.

[10]Muckell J,Hwang J H,Lawson C T,et al.Algorithms for compressing GPS trajectory data:an empirical evaluation [C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems,San Jose,USA,Nov 2-5,2010.New York,USA:ACM, 2010:402-405.

[11]Schmid F,Richter K F,Laube P.Semantic trajectory compression[M]//Advances in Spatial and Temporal Databases. Berlin,Heidelberg:Springer,2009:411-416.

[12]Richter K F,Schmid F,Laube P.Semantic trajectory compression:representing urban movement in a nutshell[J]. Journal of Spatial Information Science,2012(4):3-30.

[13]Cao Hu,Wolfson O.Nonmaterialized motion information in transport networks[C]//LNCS 3363:Proceedings of the 10th International Conference on Database Theory,Edinburgh,UK,Jan 5-7,2005.Berlin,Heidelberg:Springer,2005: 173-188.

[14]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&Applications,Washington,Jul 1-3,2012. New York:ACM,2011.

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

[16]Su Han,Zheng Kai,Zeng Kai,et al.Making sense of trajectory data:a partition-and-summarization approach[C]//Proceedings of the 2015 IEEE 31st International Conference on Data Engineering,Seoul,Apr 13-17,2015.Piscataway,USA: IEEE,2015:963-974.

JIANG Junwen was born in 1991.He is an M.S.candidate at East China Normal University.His research interests include databases and data mining.

江俊文（1991—），男，浙江衢州人，華東師范大學碩士研究生，主要研究領域為數據庫，數據挖掘。

ZHANG Kai was born in 1992.He is an M.S.candidate at East China Normal University.His research interests include databases and data mining.

張凱（1992—），男，上海人，華東師范大學碩士研究生，主要研究領域為數據庫，數據挖掘。

WANG Xiaoling was born in 1975.She is a professor and Ph.D.supervisor at East China Normal University,and the member of CCF.Her research interests include Web services and Web data management.

王曉玲（1975—），女，山東煙臺人，華東師范大學教授、博士生導師，CCF會員，主要研究領域為Web服務，數據管理技術。

JIN Cheqing was born in 1977.He is a professor and Ph.D.supervisor at East China Normal University,and the member of CCF.His research interests include data stream,location-based services and uncertain data management.

金澈清（1977—），男，浙江成縣人，華東師范大學教授、博士生導師，CCF會員，主要研究領域為數據流管理，基于位置的服務，不確定數據管理。

Trajectory Compression Based on Moving Features?

JIANG Junwen,ZHANG Kai,WANG Xiaoling+,JIN Cheqing
Institute for Data Science and Engineering,East China Normal University,Shanghai 200062,China
+Corresponding author:E-mail:xlwang@sei.ecnu.edu.cn

JIANG Junwen,ZHANG Kai,WANG Xiaoling,et al.Trajectory compression based on moving features.Journal of Frontiers of Computer Science and Technology,2016,10(9)：1240-1249.

The popularity of mobile terminals and the development of global positioning system(GPS)produce mass of trajectory data.Based on the data,a lot of location-based services(LBS)provide services for people.However,the increment of trajectory data brings many challenges:huge data volume,long query latency,hard to analyze and data redundancy.Hence the trajectory compression plays an important role for better LBS.This paper proposes a trajectory compression method which fully considers the moving features and handles trajectory as Markov sequence.The moving features include speed,direction and position.Gaussian distributionis used to model speed change,direction change and position distance,so that the status of the next point can be predicated well based on aforementioned information.According to the prediction accuracy,every point in trajectory is given a conditional self-information value.A compressed trajectory is generated by picking those points that satisfy the user-predefined value.Finally,this paper verifies the performance of the proposed compression method through a number of experiments on real datasets.

trajectory compression;moving features;self-information;Markov sequence

移動終端的普及和全球定位系統（global positioning system，GPS）的發展，產生了海量的軌跡數據。許多基于位置的服務（location-based services，LBS）利用這些軌跡數據為用戶提供服務。但是軌跡數據日益增多帶來了許多挑戰：數據量巨大，查詢延時增長，數據分析困難以及數據冗余。軌跡壓縮對于提供更好的服務是非常有必要的，因此提出了基于行駛特征的軌跡壓縮技術，考慮了行駛特征，并且把軌跡數據建模為馬爾可夫序列。行駛特征包括速度、方向和位置，使用高斯分布對速度變化、方向變化和位置距離進行建模，下一個點的狀態就能通過之前的信息來進行預測；根據預測的準確度，為每個軌跡點賦予條件自信息量；篩選出滿足用戶設定準確度閾值的點，組成壓縮后的軌跡。在真實數據集上進行了一系列的實驗，證明了算法的性能。

2015-07,Accepted 2015-11.

*The National Natural Science Foundation of China under Grant Nos.61170085,61321064,61370101(國家自然科學基金);the Shanghai Knowledge Service Platform Project under Grant No.ZF1213(上海市知識服務平臺項目).

CNKI網絡優先出版:2015-11-24,http://www.cnki.net/kcms/detail/11.5602.TP.20151124.1354.004.html

A

TP311