Compression of GPS trajectories
Enormous amounts of GPS trajectories, which record users' spatial and temporal information, are collected by geo-positioning mobile phones in recent years. The massive volumes of trajectory data bring about heavy burdens for both network transmission and data storage. For example, if data is collected at 10 second intervals, a calculation shows that without any compression, 100 Mb of storage capacity is required to store just 400 objects for a single day. To overcome these difficulties, a number of compression algorithms have been proposed by line simplification in order to reduce the size of the trajectory data.
There are already some commercial products such as on: http://onestepahead.de
We consider the problem of lossy compression for GPS trajectories with latitude, longitude and timestamp information, under a given error tolerance, i.e., synchronous Euclidean distance between the original and the compressed trajectories. In contrast to the existing trajectory compression algorithm, we achieve two significant improvements described below.
1. Speed and direction changes are used in the encoding process instead of the differential coordinates in the previous methods.
2. Line simplification and quantization are combined in the encoding process in order to optimize the approximated trajectory for compression.
The proposed algorithm has a bit-rate 0.30-0.50 KB/hour and 0.10-0.25 KB/hour for 3m and 10m max SED correspondingly.
M. Chen, M. Xu, P. Franti, "Compression of GPS Trajectories", Data Compression Conference, 62-71, Snowbird, USA, 2012 (oral). paper ppt
M. Chen, M. Xu, P. Franti, "Compression of GPS Trajectories using optimized apporixmation", submitted.
This demo is written in matlab with both command line format and GUI. Download
Beta version is released on Mar 11,2012,a bug is fixed, I am now doing code optimization and a new version will be updated soon.
Proof and details of the algorithm can be seen on this link.