  Representing the movements of objects (trips) over a network in a compact way
while retaining the capability of exploiting such data effectively is an
important challenge of real applications. We present a new Compact Trip
Representation (CTR) that handles the spatio-temporal data associated with
users' trips over transportation networks. Depending on the network and types
of queries, nodes in the network can represent intersections, stops, or even
street segments.
  CTR represents separately sequences of nodes and the time instants when users
traverse these nodes. The spatial component is handled with a data structure
based on the well-known Compressed Suffix Array (CSA), which provides both a
compact representation and interesting indexing capabilities. The temporal
component is self-indexed with either a Hu-Tucker-shaped Wavelet-tree or a
Wavelet Matrix that solve range-interval queries efficiently. We show how CTR
can solve relevant counting-based spatial, temporal, and spatio-temporal
queries over large sets of trips. Experimental results show the space
requirements (around 50-70% of the space needed by a compact non-indexed
baseline) and query efficiency (most queries are solved in the range of 1-1000
microseconds) of CTR.
