  We introduce a compressed data structure for the storage of free trajectories
of moving objects (such as ships and planes) that efficiently supports various
spatio-temporal queries. Our structure, dubbed GraCT, stores the absolute
positions of all the objects at regular time intervals (snapshots) using a
$k^2$-tree, which is a space- and time-efficient version of a region quadtree.
Positions between snapshots are represented as logs of relative movements and
compressed using Re-Pair, a grammar-based compressor. The nonterminals of this
grammar are enhanced with MBR information to enable fast queries.
  The GraCT structure of a dataset occupies less than the raw data compressed
with a powerful traditional compressor such as p7zip. Further, instead of
requiring full decompression to access the data like a traditional compressor,
GraCT supports direct access to object trajectories or to their position at
specific time instants, as well as spatial range and nearest-neighbor queries
on time instants and/or time intervals.
  Compared to traditional methods for storing and indexing spatio-temporal
data, GraCT requires two orders of magnitude less space, and is competitive in
query times. In particular, thanks to its compressed representation, the GraCT
structure may reside in main memory in situations where any classical
uncompressed index must resort to disk, thereby being one or two orders of
magnitude faster.
