Trajectory Pattern Mining: Exploring Semantic and Time Information

Abstract

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. Trajectory patterns consist of hot regions and the sequential relationships among them, where hot regions refer the spatial regions with a higher density of data points. Note that some hot regions do not have any meaning for users. Moreover, trajectory patterns do not have explicit time information or semantic information. To enrich trajectory patterns, we propose semantic trajectory patterns which are referred to as the moving patterns with spatial, temporal, and semantic attributes. Given a user trajectory, we aim at mining frequent semantic trajectory patterns. Explicitly, we extract the three attributes from a raw trajectory, and convert it into a semantic mobility sequence. Given such a semantic mobility sequence, we propose two algorithms to discover frequent semantic trajectory patterns. The first algorithm, MB (standing for matching-based algorithm), is a naive method to find frequent semantic trajectory patterns. It generates all possible patterns and extracts the occurrence of the patterns from the semantic mobility sequence. The second algorithm, PS (standing for PrefixSpan-based algorithm), is developed to efficiently mine semantic trajectory patterns. Due to the good efficiency of PrefixSpan, algorithm PS will fully utilize the advantage of PrefixSpan. Since the semantic mobility sequence contains three attributes, we need to further transform it into a raw sequence before using algorithm PrefixSpan. Therefore, we propose the SS algorithm (standing for sequence symbolization algorithm) to achieve this purpose. 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.