A low-dimensional feature vector representation for alignment-free spatial trajectory analysis

Trajectory analysis is a central problem in the era of big data due to numerous interconnected mobile devices generating unprecedented amounts of spatiotemporal trajectories. Unfortunately, datasets of spatial trajectories are quite difficult to analyse because of the computational complexity of the various existing distance measures. A significant amount of work in comparing two trajectories stems from calculating temporal alignments of the involved spatial points. With this paper, we propose an alignment-free method of rep-resenting spatial trajectories using low-dimensional feature vectors by summarizing the combinatorics of shape-derived string sequences. Therefore, we propose to translate trajectories into strings describing the evolving shape of each trajectory, and then provide a sparse matrix representation of these strings using frequencies of adjacencies of characters (n-grams). The final feature vectors are constructed by approximating this matrix with low-dimensional column space using singular value decomposition. New trajectories can be projected into this geometry for comparison. We show that this construction leads to low-dimensional feature vectors with surprising expressive power. We illustrate the usefulness of this approach in various datasets.