Supporting fast search in time series for movement patterns in multiple scales

An important investigation of time series involves searching for movement patterns, such as going up or going down or some combinations of them. Movement patterns can be in various scales: a large scale pattern may cover a long time period, while a small scale pattern usually covers a short time period. This paper considers such scale requirement. More specifically, a pattern is defined as a regular expression of letters, where each letter describes a movement direction and covers a specified length of time (called pattern unit length). To find if a time series (or a part of it) matches a pattern, the time series is first partitioned into consecutive sub-series of the unit length, and for each subseries, the direction of its best fitting line is taken as the movement direction of the sub-series if the distance between the best fitting line and the sub-series is within a specified tolerance (tolerance requirement). A direct implementation of pattern search will undoubtedly yield poor performance if the number of time series or the length of them is large. This paper introduces a pre-computation and indexing method to facilitate fast evaluation of pattern queries in user-specified scales. An efficient pre-computation algorithm is given to find the movement directions for all the sub-series that satisfy the tolerance requirement. Bounding triangles are used to represent clusters of sub-series. Relational database is then used to store these bounding triangles and relational operations are employed to facilitate the evaluation of pattern queries. The paper also reports some experiments performed on a real-life data set to show the efficiency and the scalability of the algorithms.