数据流(Data stream)已成为计算机科学与工程研究领域的一个热点,其研究范围横跨复杂性理论,算法,数据库,网络及数据挖掘等领域.在数据流模型中,一个可能无限长的数据序列以很高的速率持续到达.这些数据可能是股票价格和交易量,天文观测结果,web查询,HTTP请求以及IP地址等等. 这一特点一方面对数据流算法提出了比传统的线性时间复杂度更高的要求,如只能扫描一趟(one pass)和仅可以保存一个大小为次线性(sub-linear)(通常为对数规模)的摘要/大纲(sketch/synopsis)等等.但另一方面也允许算法输出结果有合理范围内的误差,同时允许一个非常低的出错概率. 数据流算法研究领域早期的工作主要着眼于整个数据流.然而,在很多应用场合下,同一项数据的重要性是随着时间的流逝而下降的.始终考虑整个数据流的做法就不合适了.为解决这一问题,两种数据流计算模型被提出来:滑动窗口(Sliding Window)模型和时间衰减(Time-Decaying)模型. 滑动窗口模型只考虑数据流中最新的N个数据或者最近N个小时流入的数据,N被称为滑动窗口的大小(宽度).滑动窗口模型的缺点在于一刀切,要么考虑,要么完全不考虑.考虑到在很多应用中,"Old data-never expire,they just fadeaway".这样做是很不合理的. 文中的随时间衰减模型,采用了一种权重随时间衰减的数据流统计量计算机制,每项数据对统计量的贡献随时问推移平滑下降.该模型在被用来求比平均值复杂得多的统计量如零阶频率矩,分位数和高频元素频数就需要先将数据流划分成固定的时间段.而演化模式发现和变化检测也需要将数据流中的数据项按照所处不同时间段区分开来.因此,现有的滑动窗口模型和随时间衰减模型是远远不够的. 在这篇文章中,提出了一种新的多分辨率滑动窗口模型,该模型基于一个合理的"分辨率单调性(monotonicity of resolution)"假设将数据流中的数据项按照所处不同时间段区分开来.我们的模型是传统单一滑动窗口模型有着重要意义的延伸,传统的全数据流(all-history)模型,单一滑动窗口(sliding window)模型和随时间衰减(Time-Decaying)模型均为其特例.多分辨率滑动窗口模型能够克服传统单一滑动窗口模型的缺点,但同时也给算法设计带来了新的挑战. 同时提出了在新模型下对两个重要的数据流统计量-零阶频率矩(F<,0>)和Jacard相似性系数(Jacaids similarity coefficient)-进行实时估计的数据流算法,同时对在新模型下实时监控这两个重要的数据流统计量的意义进行了讨论.算法设计需要解决的技术难题在于如何高效动态地维护原始数据流经哈希变换之后在每一个滑动窗口中的最小值或者最大值,为解决这一问题,设计了一种新颖的由一个优先队列和一个双端队列组成的核心数据结构,该数据结构很好地解决了这一‘技术难题.算法估计误差的范围在理论上有保证,并且可根据内存可得性而伸缩.新算法维护一个摘要,其空间复杂度与数据流包含数据项的个数为对数关系,与窗口的个数呈线性关系.每当一个数据项到达,算法对该摘要进行必要的更新,所需时间从摊销(amortized)的角度上与窗口的个数呈对数关系,而与算法需保证的理论误差范围近似无关.我们的算法容易实现.实验结果证实了算法的效率. 特别是,将本论文中的技术与文中的LogLog算法相结合,只要窗口的个数有一个合理的上限,在新模型下实时输出数据流所有窗口零阶频率矩所需的时间与数据流包含数据项的个数呈拟线性关系,与窗口的个数无关.有意思的是这样一个时间复杂度的结果竟然是由前面的空间复杂度结果推导而来.