Mining Frequent Trajectory Patterns in Spatial-temporal Databases

With advances in tracking technologies and great diffusion of location-based services, a large amount of data has been collected in a spatial-temporal database. The implicit knowledge in a spatial-temporal database can be used in many application areas and mining frequent trajectories in the spatial-temporal database can help us understand the movements of objects. Therefore, in this thesis, we propose a novel algorithm to mine the frequent trajectory patterns in a spatial-temporal database. Our proposed method consists of two phases. First, we transform all trajectories in the database into a mapping graph. For each vertex in the mapping graph, we record the information of the trajectories passing through the vertex in a data structure, called Trajectories Information lists (TI-lists). Second, we mine all frequent patterns from the mapping graph and TI-lists in a depth-first search manner. Our proposed method doesn’t generate unnecessary candidates, needs fewer database scans, and utilizes the consecutive property of trajectories to reduce the search space. Therefore, our proposed method is more efficient than the PrefixSpan-based method. The experiment results show that our proposed method outperforms PrefixSpan-based method by one order of magnitude in synthetic data and real data.