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

Wavelet Transformation Algorithm for Synopsis Computation in Data Stream

作　　者：欧征宇[1] 宋宝燕[2] 于亚新[1] 杨兴华[1] 苏东[1] 于戈[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004 [2]辽宁大学信息科学与工程学院,辽宁沈阳110036

出　　处：《小型微型计算机系统》2006年第11期2109-2114,共6页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术计划CIMS主题项目(2002AA1Z2308;2002AA118030)资助;辽宁省自然科学基金项目(20022027)资助;教育部优秀青年教师科研教育奖励计划资助.

摘　　要：针对数据流上近似查询中的梗概计算,提出了一种新的基于最小误差的维压缩小波变换算法(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.

关 键 词：数据流 近似查询处理 梗概计算 时间戳 小波变换 多级共享 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]