Identifying optimal multi-scale patterns in time-series streams

Abstract

A method, system, and computer readable medium for identifying local patterns in at least one time series data stream are disclosed. The method comprises generating multiple ordered levels of hierarchal approximation functions. The multiple ordered levels are generated directly from at least one given time series data stream including at least one set of time series data. The hierarchical approximation functions for each level of the multiple levels is based upon creating a set of approximating functions. The hierarchical approximation functions are also based upon selecting a current window with a current window length from a set of varying window lengths. The current window is selected for a current level of the multiple levels.

1 . A method for identifying local patterns in at least one time series data stream, the method comprising:
 generating multiple ordered levels of hierarchal approximation functions directly from at least one given time series data stream including at least one set of time series data, wherein the hierarchical approximation functions for each level of the multiple levels is based upon
 creating a set of approximating functions; and 
 selecting a current window with a current window length from a set of varying window lengths, wherein the current window is selected for a current level of the multiple levels. 
   
   
   
       2 . The method of  claim 1 , wherein the generating multiple levels of hierarchical approximation functions includes generating multiple increasing consecutive numerically ordered levels. 
   
   
       3 . The method of  claim 1 , wherein the current window is a portion of the set of time series data divided into consecutive sub-sequences, and wherein the current window length along with the hierarchal approximating functions reduces an approximation error between the current window and the set of time series data portion. 
   
   
       4 . The method of  claim 1 , wherein the current window length for the current window is larger than a current window length for a previous window in the multiple levels of hierarchal approximation functions. 
   
   
       5 . The method of  claim 1 , wherein the time series data stream is divided into non-overlapping consecutive subsequences. 
   
   
       6 . The method of  claim 1 , wherein the hierarchical approximation functions for each of level of the multiple levels is based upon further creating a set of coefficients that summarize the set of time series data portion in the current window. 
   
   
       7 . The method of  claim 1 , wherein the hierarchical approximation functions for each level of the multiple levels is based upon reusing the set of approximating functions from the previous window. 
   
   
       8 . The method of  claim 1 , wherein the hierarchical approximation functions for each of level of the multiple levels is based reducing a total squared reconstruction error, via principal component analysis. 
   
   
       9 . The method of  claim 8 , wherein total squared reconstruction error is given by equation
   Σ i=k+1   w σ i   2   /w =(Σ t=1   m   x   t   2 −Σ i=1   k σ i   2 )/ w      
     wherein k is an number of patterns chosen {1 . . . k}, wherein the patterns are vectors equal to a window length w, where m is a multiple of the window size and wherein x t  is the set of time series data portion, and wherein σ is a singular value for a given index i. 
   
   
       10 . The method of  claim 9 , further comprising using a subspace tracking algorithm to approximate incrementally at least one the following quantities
 the window length w w,   singular values of a matrix σ,   local patterns for window length w,   local approximations for each window of length w, and k.   
   
   
       11 . The method of  claim 3 , further comprising:
 calculating the approximation error between the current window and the set of time series data portion; and   basing the current window length thereon.   
   
   
       12 . A system for identifying local patterns in at least one time series data stream, the system comprising:
 at least one information processing system, wherein the information processing system includes:   a memory; and   a data stream analyzer communicatively coupled to the memory, wherein the data stream analyzer:
 generates multiple ordered levels of hierarchal approximation functions directly from at least one given time series data stream including at least one set of time series data, wherein the hierarchical approximation functions for each level of the multiple levels is based upon 
 creating a set of approximating functions; and 
 selecting a current window with a current window length from a set of varying window lengths, wherein the current window is selected for a current level of the multiple levels. 
   
   
   
       13 . The system of  claim 12 , wherein the generation of multiple levels of hierarchical approximation functions includes generating multiple increasing consecutive numerically ordered levels. 
   
   
       14 . The system of  claim 12 , wherein the current window is a portion of the set of time series data divided into consecutive sub-sequences, and wherein the current window length along with the hierarchal approximating functions reduces an approximation error between the current window and the set of time series data portion. 
   
   
       15 . The system of  claim 12 , wherein the hierarchical approximation functions for each level of the multiple levels is based upon at least one of:
 further creating a set of coefficients that summarize the set of time series data   portion in the current window;   reusing the set of approximating functions from the previous window; and   reducing a total squared reconstruction error, via principal component analysis.   
   
   
       16 . The method of  claim 14 , further comprising:
 calculating the approximation error between the current window and the set of time series data portion; and   basing the current window length thereon.   
   
   
       17 . A computer readable medium for identifying local patterns in at least one time series data stream, the computer readable medium comprising instructions for:
 generating multiple ordered levels of hierarchal approximation functions directly from at least one given time series data stream including at least one set of time series data, wherein the hierarchical approximation functions for each level of the multiple levels is based upon
 creating a set of approximating functions; and 
 selecting a current window with a current window length from a set of varying window lengths, wherein the current window is selected for a current level of the multiple levels. 
   
   
   
       18 . The computer readable medium of  claim 17 , wherein the generating multiple levels of hierarchical approximation functions includes generating multiple increasing consecutive numerically ordered levels. 
   
   
       19 . The computer readable medium of  claim 17 , wherein the current window is a portion of the set of time series data divided into consecutive sub-sequences, and wherein the current window length along with the hierarchal approximating functions reduces an approximation error between the current window and the set of time series data portion. 
   
   
       20 . The computer readable medium of  claim 17 , wherein the hierarchical approximation functions for each of level of the multiple levels is based upon at least one of:
 further creating a set of coefficients that summarize the set of time series data portion in the current window;   reusing the set of approximating functions from the previous window; and   reducing a total squared reconstruction error, via principal component analysis.