  The advances of modern localization techniques and the wide spread of mobile
devices have provided us great opportunities to collect and mine human mobility
trajectories. In this work, we focus on passively collected trajectories, which
are sequences of time-stamped locations that mobile entities visit. To analyse
such trajectories, a crucial part is a measure of similarity between two
trajectories. We propose the time-window Frechet distance, which enforces the
maximum temporal separation between points of two trajectories that can be
paired in the calculation of the Frechet distance, and the metric-based edit
distance which incorporates the underlying metric in the computation of the
insertion and deletion costs. Using these measures, we can cluster trajectories
to infer group motion patterns. We look at the $k$-gather problem which
requires each cluster to have at least $k$ trajectories. We prove that k-gather
remains NP-hard under edit distance, metric-based edit distance and Jaccard
distance. Finally, we improve over previous results on discrete Frechet
distance and show that there is no strongly sub-quadratic time with
approximation factor less than $1.61$ in two dimensional setting unless SETH
fails.
