基于屏蔽/汇总技术的数据流处理算法

论文摘要

与传统数据密集型应用相比，诸如网络监控系统等顺序产生的实时数据无法精确存储在数据库中，这种数据序列被称为数据流。数据流的典型特点是，其存储消耗具有潜在的无界性，其产生次序、间隔等统计特性具有不确定性，因此，数据流处理的算法需要具备以下的特点：1)算法复杂度必须是次线性的，输出结果可以是近似的；2)算法能够实时处理数据流输入。线性复杂度算法不能处理数据流的存储、查询和分析处理，因此，通过屏蔽或汇总数据流来控制次线性复杂度存储消耗成为数据流研究的重要内容。本篇论文通过对数据流上频繁项（集）发现、分布数据流并上聚合函数估算和κ-中值点（κ-median）搜寻，研究数据流处理的屏蔽和汇总的基本策略，主要贡献有：1．基于在线屏蔽策略，提出数据流上拒真的频繁项（集）发现，使用O(s-1ln(2δ-1)存储以至少1-δ概率输出频繁项；使用O(K／sln(s-1δ-1))存储可靠挖掘边界频繁项集（频繁项集的浓缩表示）；2．基于采样屏蔽策略，提出滤除分布数据流中的冗余和不一致的算法，应用min-wise哈希采样数据流而获取均匀样本集。由于获取的样本集不受分布流中冗余和不一致数据影响，能够准确估计聚合函数值，并进一步应用min—wise哈希方法采样位置流（location streams）来搜寻κ-中值点；3．基于汇总数据流策略，提出数据流上κ-中值点的快速估算算法，应用空间分割的汇总结构控制存储复杂度。不同于位置流中的频繁更新，数据流上κ-中值点需要单遍扫描庞大数目点集来获取近似中值点集。研究发现分割粒度不是影响κ-中值点近似程度的直接原因，避免精细分割产生指数增长的存储消耗问题。本文的研究成果可广泛应用于数据流相关的应用，如金融交易数据的处理、传感器网络数据的分析、以及网络实时监控等领域。

论文目录

• 中文摘要
• 英文摘要
• 图目录
• 表目录
• 第一章 引言
• 1.1 数据流特点
• 1.2 数据流处理算法的基本要求
• 1.3 数据流研究进展
• 1.3.1 数据流模型研究进展
• 1.3.2 数据流处理算法研究进展
• 1.4 数据流研究的理论和现实意义
• 1.5 论文的主要贡献和结构
• 第二章 在线屏蔽算法Ⅰ:数据流上频繁项（集）挖掘
• 2.1 基于在线屏蔽的数据流频繁项挖掘
• 2.1.1 Chernoff不等式
• 2.1.2 在线屏蔽的思路
• 2.1.3 频繁项挖掘算法
• 2.1.4 纳伪和拒真方法对比研究
• 2.2 数据流上频繁项集的挖掘
• 2.3 实验
• 2.3.1 频繁项挖掘
• 2.3.2 频繁项集挖掘
• 2.4 本章总结
• 第三章 在线屏蔽算法Ⅱ:数据流上频繁项集的压缩表示
• 3.1 问题定义
• 3.2 LN:基于在线屏蔽的可靠算法
• 3.2.1 删除条件对比
• 3.2.2 保持距离对比
• 3.3 （1-δ）-最优覆盖挖掘
• 3.4 实验
• 3.4.1 频繁项挖掘
• 3.4.2 频繁项集挖掘和δ-最优覆盖的产生
• 3.5 相关工作和本章总结
• 第四章 取样屏蔽算法Ⅰ:分布数据流并的聚合运算
• 4.1 分布流并的语义及其应用实例
• 4.1.1 分布流并的语义
• 4.1.2 应用实例
• 4.1.3 冗余和不一致
• 4.2 相关工作
• 4.3 问题定义
• 4.4 背景知识
• 4.4.1 Min-Wise哈希
• 4.4.2 Hoeffding不等式
• 4.4.3 不同实体数的估计
• 4.5 分布更新流的平均聚合估计
• i的生成'>4.5.1 局部均匀样本集（?）_i的生成
• i的生成'>4.5.2 全局均匀样本集∑（?）_i的生成
• i）'>4.5.3 估计g（∨ V_i）
• 4.5.4 算法分析和参数选取
• 4.6 其他聚合函数的估计
• 4.6.1 分布滑动窗口
• 4.6.2 估计其他的聚合函数
• 4.7 实验
• 4.7.1 实验配置
• 4.7.2 平均聚合函数的估计
• 4.7.3 跟其他方法的比较
• 4.8 本章总结
• 第五章 取样屏蔽算法Ⅱ:移动物体κ-中值点估算
• 5.1 相关工作
• 5.2 问题定义
• 5.2.1 符号表示
• 5.2.2 移动物体的近似κ-中值点
• 5.2.3 难点及其算法概述
• 5.3 算法
• 5.3.1 uMediSam:位置流上的采样
• 5.3.2 uComSam:获取全局均匀样本集
• 5.3.3 κ-中值点的估算
• 5.4 实验
• 5.4.1 实验环境和配置
• 5.4.2 影响中值点估计的因素
• 5.5 本章总结
• 第六章 基于汇总的数据流处理:数据流上κ-中值点的快速计算
• 6.1 问题定义
• 6.2 基于分割的汇总结构构建和近似度分析
• 6.2.1 基于分割的汇总结构
• 6.2.2 占优和汇总结构近似度分析
• 6.3 密度、占优和动态分割的构建
• 6.3.1 基于密度的启发规则
• 6.3.2 动态分割构建
• 6.3.3 分割的管理策略
• 6.4 实验
• 6.4.1 不同数据集上的测试
• 6.4.2 算法参数对聚类的影响
• 6.5 相关工作
• 6.6 本章总结
• 第七章 结束语
• 参考文献
• 攻读博士期间发表论文
• 致谢