Estimating similarity over data streams based on Dynamic Time Warping

Estimating similarity over data streams has many applications in the data streams environment, such as intrusion detection in the network, data analysis in the sensor net, cluster, k-nearest neighbor queries and so on. However, there has only a few research related to similarity evaluation under data stream contexts. The main reason is because of the native feature of data streams, namely, large, continuous, and only one pass scan. It is hard to find an efficient method to evaluate similarity over data streams. In this paper, we propose a new algorithm ESDS(Estimating Similarity over Data Streams), which not only can estimate similarity efficiently over data streams under the time warping distance but is the first time to use DTW(Dynamic Time Warping) distance based on the sliding window to deal with similarity evaluation over data streams. To the best of our knowledge, this paper is the first paper to address this problem. In order to evaluate the efficiency of our algorithm, we present a simple but efficiently method to denote the original stream data. In computing the distance of DTW between data streams by using dynamic programming, we also introduce a new distance of DTW which can compute the similarity over data streams efficiently. The experiments of many real and synthetic data sets show that our algorithm can evaluate the similarity over data streams efficiently and not be studied in the previous research.