3.3.2.1　数据流模型

数据流管理、查询和挖掘任务对数据结构、算法等提出了新的要求。在处理数据流时，要求设计出有效的单遍扫描算法，在有限的内存空间里不断更新能够表征数据流的概要数据结构，使得查询、挖掘算法在任意时刻都能够根据概要数据结构获得近似的且其准确性有概率保证的计算结果。

一般地，数据流处理的联机（On－line）算法主要包括两部分内容：一个是监控数据流并不断更新概要数据结构的算法；另一个是响应用户的查询请求和挖掘任务，并且能实时地计算得到近似结果的算法。在此，相关的算法要能够以一定概率保证计算结果的误差被限制在一个小的范围内。同时，由于内存空间的限制，要求概要数据结构模型的复杂度至多是次线性的。根据数据流的特点可知，数据结构模型的及时更新问题是数据流技术要解决的关键问题之一。

在进行数据流计算时，有哪些数据被包含在计算范围之内，关于这个问题，按照算法处理数据流时所采用的时序范围，数据流模型可分为以下几类：

（1）快照模型：处理数据的范围限制在两个预定义的时间戳之间；

（2）界标模型：处理数据的范围从某一个已知的初始时间点到当前时间点为止；

（3）滑动窗口模型：处理数据的范围由某个固定大小的滑动窗口确定，此滑动窗口的终点永远为当前时刻，其中滑动窗口的大小可以由一个时间区间定义，也可以由窗口所包含的数据项数目定义。

3.3.2.2　数据流概要描述(www.daowen.com)

为了在正确性与存储空间之间进行平衡，可以对数据流进行概要描述，即保存数据流的压缩信息，使得在任何时候都能根据数据的概要描述获得满足查询要求的近似结果。对数据流的概要描述一般采用大纲数据结构。生成概要数据结构的常用技术主要包括：随机抽样、滑动窗口、直方图、小波技术、哈希方法、梗概技术等。

（1）随机抽样是指对数据流进行周期区间随机取样，从数据集中随机抽取一小部分数据作为整个数据集的样本，根据该样本集合获得近似查询结果；

（2）滑动窗口是对最近的数据进行计算，设窗口“大小”或长度为w，每个时刻t都有新元素到来，则该元素在t＋w时刻“过期”，可以根据窗口中未过期的元素得到近似查询结果；

（3）直方图技术是将数据按照数据项的值域或出现频率划分为一系列相邻的桶，使用这些直方图来产生近似查询结果；

（4）小波技术是一种信号处理技术，小波变换可以将输入的信号变换成一系列小波参数，提取其中的少数几个高能量参数，近似还原原始信号；

（5）哈希方法是通过一组哈希函数，将大量数据从一个范围映射到另一个范围中去，使用一小块远小于数据集数据范围的内存空间表示数据集；

（6）梗概技术是对数据进行垂直取样，基于散列的技术，即沿着某一维投影以实现维数约减的方法，梗概划分以可保证的误差，使用基本数据的粗略统计信息来智能地划分属性的定义域。