An Efficient Trajectory Compression Algorithm for Moving Objects

這篇介紹壓縮GPS軌跡點的演算法，這篇的PATCH演算法改良自 SQUISH-E :

J. Muckell, P. Olsen, J. Hwang, C. Lawson, and S. Ravi,“Compression of trajectory data: a comprehensive evaluation and new approach.”Geoinformatica, vol. 18, no. 3, pp. 435-460, 2014

PATCH壓縮方式是截彎取直，同時有最小的誤差，不會和原來軌跡的形狀差太多。

壓縮率計算方法: R=(1-(a/b)) x 100%



下列是PATCH演算法總覽，其中Filtration()、Divergence_Identification()、Neighbour_Calculation()分成三個Algorithm描述。

 Filtration利用Sliding Window的方式，一個一個GPS point塞到priority queue，達到最大容量時，還會繼續塞，但會把低priority的point移除。

Divergence_Identification會將前一個步驟(Filtration)的路線轉向關鍵point，決定保留或移除。

Neighbour_Calculation檢查Divergence_Identification 輸出的point數量，如果沒有達到參數的數量，就重跑Filtration，將之前過濾掉的拿出來再重新考慮，直到達到參數設定的數量。