PartSpan: Parallel Sequence Mining of Trajectory Patterns

The trajectory pattern mining problem has recently attracted increasing attention. This paper precisely addresses the parallel mining problem of trajectory patterns as well as the newly proposed concepts with regard to trajectory pattern mining. An efficient parallel trajectory sequential pattern mining (PartSpan) is proposed by incorporating three key techniques: prefix-projection, parallel formulation, and candidate pruning. The prefix-projection technique is used to decompose the search space as well as greatly reducing candidate trajectory sequences. The parallel formulation integrates the data parallel formulation and the task parallel formulation to partition the computations and to assign them to multiple processors in an efficient and effective manner that helps reduce the communication cost across processors. Representative experiments are used to evaluate the performance of PartSpan. The results show that PartSpan outperforms GSP-based and SPADE-based parallel algorithms in mining very large trajectory databases.