Efficient pattern matching with periodical wildcards in uncertain sequences

Data uncertainty is inherent in many real-world applications such as sensor data monitoring and mobile tracking. Mining sequential patterns from uncertain/inaccurate data, such as sensor readings and GPS trajectories, is important to discover hidden knowledge in such applications. This paper addresses the problem of pattern matching with periodical wildcards for uncertain sequences. We present a dynamic programming approach, called CoDP, to compute the exact probability that a pattern q is a subsequence of an uncertain sequence s, and this approach can be further applied to substring matching for uncertain sequences. The efficiency and effectiveness of our algorithm have been verified through extensive experiments on both real and synthetic data.