Matching stream patterns of various lengths and tolerances

Continuously identifying pre-defined patterns in a streaming time series has strong demand in various applications. While most existing works assume the patterns are in equal length and tolerance, this work focuses on the problem where the patterns have various lengths and tolerances, a common situation in the real world. The challenge of this problem roots on the strict space and time requirements of processing the arriving and expiring data in high-speed stream, combined with difficulty of coping with a large number of patterns with various lengths and tolerances. We introduce a novel concept of converging envelope which bounds the tolerance of a group of patterns in various tolerances and equal length and thus dramatically reduces the number of patterns for similarity computation. The basic idea of converging envelope has potential to more general index problems. To index patterns in various lengths and tolerances, we partition patterns into sub-patterns in equal length and an multi-tree index is developed in this paper. Copyright 2009 ACM