一种基于滑动窗口的数据流相似性查询算法

相似性查询是一种非常重要的数据挖掘应用。由于数据流具有无限、高速等特性，传统的查询算法不能直接应用于数据流。提出了一种基于小波滑动窗口的多数据流相似性查询算法。算法首先将滑动窗口划分成若干等宽基本窗口，然后对每个基本窗口内的数据进行小波分解与系数约简，从而形成小波摘要窗口。执行相似性查询时，直接基于小波摘要进行计算，而无需数据重构。由于利用了小波分解的线性处理优点，算法具有较低的时间复杂度。最后，基于实际数据对算法进行了实验，实验结果证明了算法的有效性。

Algorithm Based on Sliding Window for Similarity Queries over Data Stream

Similarity queries are fundamental part of modern data mining application. But traditional ctuery algorithms can not be applied on data stream, which is an unbounded sectuence of data elements generated at a rapid rate. We proposed a novel approach for computing similarity over multi data streams based on wavclet sliding window model. The basic idea is to divide sliding window into equally-sized basic windows and represent the data elements of a basic window using wavelet coefficients, then form wavelet synopses window. As a result, queries toward data streams can be converted to queries toward such wavelet synopses. This algorithm takes advantage of the merit of wavelet decomposition for linear computing and achieves superior runtime performance. The extensive experiments verified the effectiveness of our algorithm.