Efficient Trajectory Compression and Queries

Nowadays, there are ubiquitousness of GPS sensors in various devices collecting, storing and transmitting tremendous trajectory data. However, an unprecedented scale of GPS data has posed an urgent demand for not only an effective storage mechanism but also an efficient query mechanism. Line simplification in online mode, a kind of commonly used trajectory compression methods in practice, plays an important role to attack this issue. But for the existing algorithms, either their time cost is extremely high, or the accuracy loss after the compression is too much. To address this, we propose $\epsilon$-Region based Online trajectory Compression with Error bounded (ROCE for short), which makes the best balance among the accuracy loss, the time cost and the compression rate. In most previous work, each trajectory is seen as a sequence of discrete points for various queries. But it's not suitable when the queried trajectories have been compressed, because there may be hundreds of points discarded between each two adjacent points and the points in each compressed trajectory are quite sparse. To attack this issue, in this paper, each compressed trajectory is regarded as a sequence of continuous line segments, but not discrete points. And based on this, we propose a new trajectory similarity metric AL, an efficient index ASP-tree and two algorithms about how to process range queries and top-k similarity queries on the compressed trajectories. Extensive experiments have been done on real datasets and the results demonstrate superior performance of our methods.