A Disk-Based Index for Trajectories with an In-Memory Compressed Cache

Daniela Campos, Adrián Gómez-Brandón, and Gonzalo Navarro

We present a representation of trajectories moving through the space without any constraint. It combines an in-memory cached index based on compact data structures and a classic disk-based strategy. The first structure allows some loss of precision that is refined with the second component. This approach reduces the number of accesses to disk. Comparing it with a classical index like the MVR-tree, this structure obtains competitive times in queries like time slice and knn, and sharply outperforms it in time interval queries. In addition it can solve other queries not supported with the MVR-tree. The space usage of our structure is 24 times less than that of the classical spatio-temporal index.