一种适用于数据流梗概计算的小波变换算法

Wavelet Transformation Algorithm for Synopsis Computation in Data Stream

针对数据流上近似查询中的梗概计算,提出了一种新的基于最小误差的维压缩小波变换算法(MEDC).MEDC算法通过映射流数据时间戳,快速无冗余地维护流数据的有序性;基于最小误差,高效压缩小波变换阵列,最大化MEDC算法时间效率及近似查询实时处理能力;引入小波系数与查询准确度之间的数值性关联规则,支持小波系数梗概上的查询多级共享,整体查询执行性能最佳.实验表明,与传统小波变换、直方图和采样等算法相比,MEDC算法在数据流近似查询处理的响应速度、查询结果质量等方面具有更为优越的性能.

Aiming at synopsis computation of approximate query in data stream, a novel wavelet transformation algorithm, Minimum Error based Dimension Compression （MEDC） algorithm, is proposed in this paper. On account of effective use of streaming datars time-stamp, MEDC can retain the sequence of streaming data quickly without redundancies. Besides, MEDC sharply reduces time costs and maximizes queriesr capability in real-time processing as a result of efficient compression on wavelet transform array. Last but not least, MEDC develops a novel association rule, which results in the multi-level sharing query on data synopsis and great improvement on query processing performance. Compared with traditional wavelets, histograms and sampling, the experimental results demonstrate that MEDC provides better quality of approximate answers but requires less response-time.