北京林业大学 信息学院，北京 100083

北京林业大学 信息学院，北京 100083

1 引言

数据流数据的处理近年来得到越来越广泛的重视，其原因在于，随着网络技术的发展，在电子商务，网络监控，证券股票、无线通信网等等，数据流成为一种较为普遍的信息传送方式。数据流是一组顺序、大量、快速、连续到达的数据序列，是一种特殊的数据类型。由于数据流是连续到达且具有无限性，有限的处理机不可能保存数据的全部信息。另一方面，对于某些系统，比如对于设备或场景监控的应用，这类数据往往呈现多点并发，流量巨大等特点，而且数据流的信息中往往含有大量的冗余，可能大多数情况下时间序列中的数据是有很强的关联性的，甚至是相等的[1]。在保证数据精度的情况下，采用正确的方法对数据流进行描述，不仅是发现数据关联的有效途径，对于压缩数据量，减少系统存储压力，加快数据查询速度，也具有重要的意义。

目前，对于流数据处理普遍的做法是在存储器中开辟一个滑动窗口来保存近期到达的数据流数据，以实时地支持查询请求。随着数据流不断地流入滑动窗口，当滑动窗口数据已满时，将会有部分旧数据从滑动窗口中流出。流出滑动窗口的这部分数据称为历史数据。基于数据流历史数据的压缩处理算法已经有了一些研究结果。这些研究方法都是基于抽样的，但是在很多情况下，常常需要保存连续的数据[2]。因此，抽样的方法并不能满足这种需求。……