论文部分内容阅读
数据流是指一系列实时、高速、持续到来的输入数据项.近年来,数据流因其广泛出现在网络业务流、传感器网络、大规模天文观测、金融即时行情以及各种记录日志中而备受关注.数据流高速、海量的特点带来了算法及应用层面的众多根本性问题.其中,计算高频项是计算机网络、数据库和数据挖掘领域共同面对的最重要问题之一,然而要在有限存储空间内实时监测大流量数据的高频项却是一个极大的挑战.该文在充分研究各种数据流基本模型和算法策略的基础上,给出了两种计算无限数据流高频项的改进算法,提出了一种计算滑动窗口数据流高频项的近似算法,设计了一个基于窗口的数据流高频项实时监测系统.高频项监测是指在任何时刻都能计算出当前出现频率超过指定阈值的数据项.该文经过分析对比发现,在各种算法策略中计数方法是最适合于解决高频项监测问题的有效方法.数据流可以分成无限数据流和窗口数据流两种.无限数据流计算对象是整条输入数据流,在无限数据流下统计高频项的困难在于数据项种类太多以致内存需求无法满足.为此,该文在保证算法具有常数误差界的前提下,对现有的两种采用计数策略的弱近似算法提出了改进.实验结果表明改进算法在近似解精度,时间和空间效率上均有不同程度的改善与提高.滑动窗口数据流是一种时间敏感数据流,它只计算新近出现的w个项,更符合实际网络业务流的应用.但使用滑动窗口需要隐式删除过期数据项,这导致需要Ω(w)存储空间.因此,该文给出了一种具有可控近似度的single-pass算法,有效降低了存储空间.另外,有时候用户还要对比高频项的变化趋势,为此该文又引入了多尺度时间窗口思想,利用多尺度时间窗口可以监测中长期高频项的出现情况.综合滑动窗口和多尺度时间窗口两种策略,该文设计了一个基于窗口的网络业务流高频项监测原型系统,该系统仅用少量内存即可同时监测短、中、长期高频项的出现情况.