一种基于滑动窗口的数据流摘要构造算法

An Algorithm for Construction of Synopses over Data Stream Based on Sliding Windows

由于数据流具有无限、高速等特性,使得对数据流的查询处理往往不是面向整个数据流,而是把查询处理的范围限定在某个可操作的范围内,比如一个数据窗口。另一方面,通过数据摘要近似表达数据,也是数据流查询处理应对存储空间约束的常用策略。本文提出一种基于滑动窗口的数据流小波摘要构造算法,利用了窗口技术与数据摘要技术的优点。算法的基本思路是基于滑动窗口模型,将数据流划分成若干等宽基本窗口,每个基本窗口内数据进行小波分解与系数约简,从而形成滑动小波摘要窗口。为使窗口内数据摘要绝对重构误差最优,定义一个系数删减标准,采用贪心策略对窗口内小波系数逐步求精,从而获得最优绝对误差小波摘要。实际应用结果证明了算法的有效性。

Because of its limitless and high rate,data stream is always processed within a limited range such as a data window.On the other hand,construction of synopses for data stream is always a good choice to copy with the limitation of store space.This paper proposes an algorithm for construction of synopses over data stream basing on sliding windows,which takes advantage of the merit of windows technology and synopses.The basic idea of the algorithm is to divide data stream into equally-sized basic windows and represent the data elements of a basic window using reduced wavelet coefficients.For getting the synopses with optimal maximum absolute error,the algorithm defines a parameter to reduce wavelet coefficients using a greedy strategy.At last,the wavelet synopses of data stream with optimal absolute error are got.The practical application verifies the efficiency of the algorithm.