GraCT: A Grammar based Compressed representation of Trajectories
  We present a compressed data structure to store free trajectories of moving objects (ships over the sea, for example) allowing spatio-temporal queries. Our method, GraCT, uses a $k^2$-tree to store the absolute positions of all objects at regular time intervals (snapshots), whereas the positions between snapshots are represented as logs of relative movements compressed with Re-Pair. Our experimental evaluation shows important savings in space and time with respect to a fair baseline. 
Nieves R. Brisaboa, Adri\'an G\'omez-Brand\'on, Gonzalo Navarro,   Jos\'e R. Param\'a
cs.DS