  We study the problem of finding the $k$ most similar trajectories to a given
query trajectory. Our work is inspired by the work of Grossi et al. [6] that
considers trajectories as walks in a graph. Each visited vertex is accompanied
by a time-interval. Grossi et al. define a similarity function that captures
temporal and spatial aspects. We improve this similarity function to derive a
new spatio-temporal distance function for which we can show that a specific
type of triangle inequality is satisfied. This distance function is the basis
for our index structures, which can be constructed efficiently, need only
linear memory, and can quickly answer queries for the top-$k$ most similar
trajectories. Our evaluation on real-world and synthetic data sets shows that
our algorithms outperform the baselines with respect to indexing time by
several orders of magnitude while achieving similar or better query time and
quality of results.
