Mining frequent trajectory pattern based on vague space partition

摘要

Frequent trajectory pattern mining is an important spatiotemporal data mining problem with broad applications. However, it is also a difficult problem due to the approximate nature of spatial trajectory locations. Most of the previously developed frequent trajectory pattern mining methods explore a crisp space partition approach [8], [10] to alleviate the spatial approximation concern. However, this approach may cause the sharp boundary problem that spatially close trajectory locations may fall into different partitioned regions, and eventually result in failure of finding meaningful trajectory patterns. In this paper, we propose a flexible vague space partition approach to solve the sharp boundary problem. In this approach, the spatial plane is divided into a set of vague grid cells, and trajectory locations are transformed into neighboring vague grid cells by a distance-based membership function. Based on two classical sequential mining algorithms, the PrefixSpan and GSP algorithms, we propose two efficient trajectory pattern mining algorithms, called VTPM-PrefixSpan and VTPM-GSP, to mine the transformed trajectory sequences with time interval constraints. A comprehensive performance study on both synthetic and real datasets shows that the VTPM-PrefixSpan algorithm outperforms the VTPM-GSP algorithm in both effectiveness and scalability.