王宝军 詹英

摘要： 对于许多应用领域不断产生的数据流,面向数据流聚集查询的应用最为广泛。本文在构造压缩桶的基础上，提出了基于时间维度压缩数据流的算法，来动态地形成压缩数据流,并进一步给出了使用压缩桶获得数据流聚集查询的数学方法。

关键词： 数据流； 压缩桶； 聚集查询； 时间维度

中图分类号：TP393文献标识码：A 文章编号：1006-8228（2012）04-29-03

Aggregate compression algorithm for data stream

Wang Baojun, Zhan Ying

（Zhejiang Institute of Communications， Hangzhou， Zhejiang 311112， China）

Abstract： In many fields, data stream continues to grow in terms of generation speed. Aggregate query for data stream was most widely used. By constructing compression buckets, the authors provides in this paper a compression algorithm for data stream based on time dimension, in order to dynamically form compression data stream, and give mathematical method of aggregate query for data stream, by use of compression buckets.

Key words： data stream； compression buckets； aggregate query； time dimension

0 引言

数据流是随着网络的广泛应用而出现的一种新的数据形式。数据流聚集查询是数据流管理与知识发现系统中一种重要的数据知识发现模型，但快速流动的流数据与有限的处理能力之间的矛盾使得流数据的聚集查询分析比关系数据库的聚集分析更困难。

目前国内外已经对数据流聚集查询模式展开了研究。Dobra A等人研究利用随机草图技术，提取数据流的轮廓，减少数据的处理量来加快数据处理速度，并提出了一种草图分割技术来提高算法的性能[1]。Gilbert A C等人研究采用小波技术对数据流进行压缩，实现了近似聚集查询[2]。Madden研究了传感器网络中的聚集查询问题，重点是如何动态地建立路由树，实现流水线聚集操作[3，4]。Ahnad Y提出了数据流查询的分布式操作[5]。张冬冬等人提出了一种新的数据流传输方式，有效地减少网络中分布式数据流的传输量[9]。傅鹂等人建立了基于数据流驱动的数据流连续查询模型，设计并使用查询算子在查询链中的有序组合来构造出各种复杂的连续查询语句[7]。李建中等人提出利用多元线性回归方法来预测具有线性关系的数据流的未来聚集值，但如果数据不具有线性关系，该模型误差就会增大[10]。……