Mining Probabilistic Frequent Spatio-Temporal Sequential Patterns with Gap Constraints from Uncertain Databases

Uncertainty is common in real-world applications, for example, in sensor networks and moving object tracking, resulting in much interest in item set mining for uncertain transaction databases. In this paper, we focus on pattern mining for uncertain sequences and introduce probabilistic frequent spatial-temporal sequential patterns with gap constraints. Such patterns are important for the discovery of knowledge given uncertain trajectory data. We propose a dynamic programming approach for computing the frequentness probability of these patterns, which has linear time complexity, and we explore its embedding into pattern enumeration algorithms using both breadth-first search and depth-first search strategies. Our extensive empirical study shows the efficiency and effectiveness of our methods for synthetic and real-world datasets.