数据流变化的检测

Detecting Change of Data Stream

通过对数据流的两个相邻窗口的比较,检测出绝对变化较大的元素,以此来描述流数据的变化。把单个窗口中的数据流划分成若干层,在每层上对数据值域进行分段。然后在每层上定义若干分段集合,并对分段集合进行求和运算。通过对两个窗口的概要结构进行合并,采用二分法,利用集合的分解,可以求得变化较大的元素。理论和实验证明,本算法利用对数空间有效地解决了数据流中变化较大元素的检测问题。

Detecting change of data stream plays an important role in many data stream＇ s decision support systems. The change of data stream is described by detecting the elements whose value difference between two adjoining windows exceeds threshold value. Single window data stream is divided into several levels, each of which partitions all elements into some groups. Some supersets over groups are defined,and the sum is calculated for each group. After combining sketches of two windows, the elements whose value exceeds threshold value are detected by performing binary search. Theory and experiments prove that the algorithm is accurate and effective for detecting change of data stream.