流数据统计算法研究

论文摘要

流数据是近年来出现的一种新型的数据模型,在许多应用领域出现频繁,表现形式各异,例如:网络监测时的IP数据包、股票分析时的股票信息、电信公司的通话记录、传感器网络发送的信号等等。与传统的数据模型相比,流数据具有如下特点:实时到达,速率多变;连续到达,次序独立;规模宏大,不能预知其极值;一经处理,除非特意保存,否则不能再次取出处理。这些特点导致了流数据不能全部保存,只能实时地单遍访问。与传统数据库应用系统相比,流数据应用系统往往需要支持连续查询和近似结果统计。因此,无法利用传统数据库技术有效地管理流数据,越来越多的研究人员开始对流数据的相关问题进行研究。流数据的统计反映了流数据的当前状态,在许多决策系统中扮演着重要的角色,同时也是流数据挖掘的一个重要基础。由于流数据的独特性,传统统计算法不适用于流数据。因此,流数据统计已成为一个迫切需要解决的问题。基于滑动窗口模型,给出了一种优化的指数级直方图--松散性指数级直方图和结构维持算法。利用对数空间,该方案解决了流数据的实时近似求和问题,相比已有方法,有明显的时空优势。把松散性指数级直方图应用到流数据计数问题上,充分考虑了流数据的相似度,定义了相似度函数,设计了一种系统框架,给出了一种解决最近N个流数据元素个数统计问题的算法,该算法保证相对误差不大于指定阈值,且流数据相似度越大,时空优势越明显。对于最大（小）值的统计问题,设计了一种算法,该算法利用链式结构,动态维护当前活动窗口中的最大值,针对内存利用过大的情况,给出了压缩策略,该算法利用少量的空间,解决了滑动窗口模型下的流数据最大值统计问题。相比聚集统计,热门元素统计更能准确地描述流数据的当前状态。给出了两种单遍访问算法--梯形过滤算法和波浪筛选算法,解决了滑动窗口模式下的流数据热门元素统计问题,保证统计结果不会遗漏任何满足条件的热门元素。梯形过滤算法应用指数级直方图来统计流数据元素的出现次数,对直方图实行周期性的压缩以删除不需要的元素和统计,该算法尤其适于分布不均匀的流数据,在此情况下,即使滑动窗口的尺寸增加,候选数据集尺寸仍保持稳定。波浪筛选算法通过对子窗口进行周期性地创建和删除,来统计元素的出现次数,其中每个子窗口拥有一个独立的概要数据结构,对每一次查询,该算法保证输出的数据个数不会过多。相比前两种统计,密度估计更能详实地反映流数据的当前状态--流数据的分布特点。基于核心密度估计法,给出了一种适合流数据特点的密度估计算法。该算法利用远远小于数据长度的空间,通过对流数据进行窗口划分,为单个窗口保留少量的分布信息,再综合所有窗口信息,从而对流数据的密度分布进行实时评估。以上的统计都反映了流数据的当前状态,而没有描述出流数据状态的变化情况,为此设计了一种流数据变化检测方案。该方案采用在两个相邻窗口中出现次数变化大的元素来描述流数据的变化:首先,把单个窗口中的流数据划分成若干层,在每层上对元素值域进行分段;然后,在每层上定义若干分段集合,并对分段集合进行求和运算;最后,通过对两个窗口的概要结构进行合并,利用集合分解,求得出现次数变化大的元素,以描述流数据的变化情况。该方案以一定的概率,输出满足条件的元素,而需要的空间却远远小于流数据尺寸。

论文目录

• 摘要
• Abstract
• 图形列表
• 表格列表
• 1 引言
• 1.1 迫切性
• 1.2 特征
• 1.3 要求
• 1.4 应用
• 1.5 应用技术
• 1.6 流数据历史
• 1.7 论文结构
• 1.8 小结
• 2 流数据统计研究现状
• 2.1 流数据统计的特点
• 2.2 流数据统计的相关工作
• 2.3 流数据管理系统发展概况
• 2.4 小结
• 3 流数据聚集统计
• 3.1 滑动窗口的引入
• 3.2 指数级直方图（Exponential histogram）
• 3.3 流数据求和统计
• 3.4 流数据个数统计
• 3.5 流数据的最大（小）值统计
• 3.6 小结
• 4 流数据热门元素统计
• 4.1 流数据热门元素
• 4.2 问题定义
• 4.3 相关工作
• 4.4 梯形过滤算法
• 4.5 波浪筛选算法
• 4.6 小结
• 5 流数据密度估计
• 5.1 流数据密度估计
• 5.2 相关工作
• 5.3 流数据密度估计算法
• 5.4 算法分析
• 5.5 实验
• 5.6 小结
• 6 流数据变化检测
• 6.1 流数据的变化
• 6.2 问题定义
• 6.3 相关工作
• 6.4 变化检测算法
• 6.5 理论分析
• 6.6 实验
• 6.7 小结
• 7 总结和展望
• 7.1 论文总结
• 7.2 研究展望
• 致谢
• 参考文献
• 附录 1 攻读学位期间发表的论文目录
• 附录 2 攻读学位期间参与的科研项目