Mining Spatial-Temporal Semantic Trajectory Patterns from Raw Trajectories

With the development of GPS and the popularity of smart phones and wearable devices, users can easily log their daily trajectories. Prior works have elaborated on mining trajectory patterns from raw trajectories. However, trajectory patterns do not have explicit time information or semantic information. To enrich trajectory patterns, we propose STS-TPs (standing for Spatial-Temporal Semantic Trajectory Patterns) which refer to the moving patterns with spatial, temporal, and semantic attributes. Given a set of user trajectories, we aim at mining STS-TPs. Explicitly, we extract the three attributes from raw trajectories, and convert these trajectories into semantic trajectory sequences. Given a set of such semantic trajectory sequences, STS-TPs could be viewed as sequential patterns with multiple attributes. To fully explore the efficiency of PrefixSpan on sequential pattern mining, we propose a PrefixSpan-based algorithm (abbreviated as PS) to discover STS-TPs. Note that the input for PrefixSpan is a set of sequences consisting of items. However, each item of semantic trajectory sequences contains three attributes, and we need to further transform these sequences into symbolized sequences before using PrefixSpan. Therefore, we propose two algorithms of Sequence Symbolization (SS) and Advanced Sequence Symbolization (ASS) to achieve this purpose. In light of STS-TPs, we further propose query tasks to predict users' behaviors. To evaluate our proposed algorithms, we conducted experiments on the real datasets of Google Location History, and the experimental results show the effectiveness and efficiency of our proposed algorithms.

I. Introduction

With the popularity of GPS sensor embedded devices such as smart phones and wearable devices, it is more convenient for users to log their daily trajectories. For example, by turning on the service of the Google Location History in the smart phone, users can record their locations, and these location records are raw trajectories. From the raw trajectories, one could infer users' daily movement behavior and spatial regions in which they frequently appear. Prior works [1] [2] have proposed trajectory pattern algorithms to discover frequent movement sequences that represent locations and sequential relationships among locations. We claim that such a trajectory pattern could be extended to include not only spatial information but also temporal and semantic information. With more information associated with movement sequences, one could have more insights into user movement behavior.