数据流分析关键技术研究

论文摘要

随着硬件、网络与通信技术的飞速发展和现实应用需求的持续推动,数据流（Data Stream）作为一种新的数据类型,在诸如金融分析、网络数据管理、移动对象跟踪、通信网监控和传感器网络数据处理等众多领域有着广泛的应用。传统的数据库查询处理技术通常只适合处理存储在磁盘或内存等介质中的静态数据,难以直接应用到无限、连续、快速、“单遍扫描”的数据流中,因而,数据流应用对数据管理与分析提出了更高的要求。如何从海量流数据中快速提取有价值的信息已成为数据库及相关研究领域面临的一个重大挑战。数据流相关研究已经引起了学术界和工业界的广泛关注,现有的研究可大致分为数据流管理和数据流分析两个方面。本文在总结和分析国内外已有研究工作的成果与不足的基础上,针对数据流分析中的四个重要问题:离群点检测、Skyline计算、子序列匹配和高效索引结构,展开深入研究,主要工作包括:1.在分布式数据流离群点检测方面。在比较和分析现有离群点度量的基础上,结合核密度估计技术扩展了基于距离和基于密度的离群点定义。针对分布式数据流离群点检测中面临如何提高全局离群点检测率和降低网络通信开销的两大问题,以常见的星型网络拓扑模型为基础,提出了一种高检测率、低通信开销的分布式数据流离群点检测算法—DisOutlierStreams。采用非参数核密度估计技术快速计算出当前滑动窗口内流数据的概率密度函数,结合指数衰减策略处理数据流的动态演化性,通过散度技术（Divergence Technology）在检测率可控的前提下较大地减少了协调结点与其子结点之间的通信开销。在算法的具体实现上,充分发挥了Matlab软件强大的符号和数值计算功能。理论分析和实验结果表明,与已有同类数据流离群点检测算法相比,该方法的网络传输量与滑动窗口大小无关,更有效地降低了网络通信开销,具有良好的性能和可扩展性。2.在数据流稀疏Skyline计算方面。由于Skyline集合的平均数目与数据点数和数据维数成指数增长,并受数据分布的严重影响,从而Skyline集合的急速增长严重降低了在线服务和决策支持等应用的服务质量。针对该问题,首先在总结已有Skyline计算的相关工作基础上,采用一个Skyline点来代表其周围在可接受偏差δ邻域内的所有Skyline点,给出了数据流稀疏Skyline问题的形式化定义。然后,提出了两个算法:基于界限裁剪的BSS算法和基于特征树的ESS算法。前者以现有数据流Skyline算法为基础,通过界限裁剪策略降低稀疏Skyline的计算开销;而后者则直接对滑动窗口内的流数据构建其稀疏Skyline特征索引树,并支持增量更新、可根据数据分布自适应地调整稀疏Skyline的计算结果。最后实验结果表明,与BSS算法相比,ESS算法具有更强的可控性和更高的处理效率。3.在数据流子序列匹配方面。子序列匹配问题在时间序列数据库中早有研究,但数据流子序列匹配还处于发展初期。本文在总结并分析现有序列匹配度量差异的基础上,选用抗噪音和形变效果良好的动态时间弯曲距离（Dynamic Time WarpingDistance）作为序列匹配的衡量标准,将数据流子序列匹配归纳为“最佳匹配”、“区域匹配”、“最优区域匹配”和“Top-K最优区域匹配”四个子问题。针对已有数据流子序列匹配算法中时间弯曲矩阵计算开销过大的问题,提出了一种低时空复杂度、近实时的数据流子序列匹配算法—FSM,它充分利用相似性阈值和上下界剪枝技术尽量减少时间弯曲矩阵中的冗余计算。理论分析和实验结果表明,与已有数据流子序列匹配算法相比,算法准确率并未有任何降低,在合理设置相似性阈值和查询序列的情况下,仅需增加几个字节的空间开销,计算速度提高明显,特别是在高维流数据和长查询序列下性能提升更为显著。4.在数据流索引结构方面。索引技术是提高数据流查询与分析性能的关键技术之一。本文在比较并分析现有支持数据流频繁更新的R-Tree变种索引的基础上,针对数据流索引结构更需同时考虑如何提高索引更新性能和降低索引存储开销的问题,提出了改进的高效数据流索引结构—QDM-Tree,并给出了相应的数据插入、删除和查询算法。该索引树利用Hash表替换耗时的索引遍历,并支持数据流的Lazy组删除策略;采用“自底向上”的索引更新方式,并结合R-Tree结点的量化压缩技术。实验结果表明,与已有同类索引树相比,QDM-Tree的存储开销与之相当,而更新和查询的性能均有明显的提升。综上所述,本文针对数据流分析中四个关键问题提出了更为高效的解决方法,并就其计算、存储、通信等开销作了全面的分析,对于数据流的理论研究和实用化具有一定的理论意义和应用价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 应用背景
• 1.1.2 数据流概念与技术
• 1.2 数据流相关研究工作
• 1.2.1 数据流管理
• 1.2.2 数据流分析
• 1.2.3 研究现状总结
• 1.3 本文工作
• 1.3.1 主要研究内容
• 1.3.2 主要创新点
• 1.4 论文结构
• 第二章 分布式数据流离群点检测
• 2.1 问题描述
• 2.1.1 离群点定义
• 2.1.2 分布式数据流离群点检测问题
• 2.2 离群点检测相关工作
• 2.2.1 离群点检测算法分类
• 2.2.2 数据流离群点检测相关工作
• 2.3 核密度估计技术
• 2.3.1 一维核密度估计
• 2.3.2 多维核密度估计
• 2.3.3 核密度估计的参数选择
• 2.4 基于核密度估计技术的离群点定义
• 2.5 改进的指数衰减策略
• 2.6 降低网络通信开销的方法
• 2.7 DisOutlierStreams 算法
• 2.7.1 子结点处理算法描述
• 2.7.2 协调结点处理算法描述
• 2.8 实验
• 2.8.1 实验设置
• 2.8.2 实验结果
• 2.9 本章小结
• 第三章 数据流稀疏Skyline 计算
• 3.1 问题描述
• 3.1.1 Skyline 问题
• 3.1.2 稀疏Skyline 问题
• 3.2 Skyline 计算相关工作
• 3.2.1 全空间Skyline 计算
• 3.2.2 子空间Skyline 计算
• 3.2.3 数据流Skyline 计算
• 3.3 基于界限裁剪的基本方法——BSS 算法
• 3.4 基于特征树的增强方法——ESS 算法
• 3.4.1 稀疏Skyline 特征树
• 3.4.2 ESS 算法描述
• 3.4.3 自适应调整策略
• 3.5 实验
• 3.5.1 实验设置
• 3.5.2 实验结果
• 3.6 本章小结
• 第四章 数据流快速子序列匹配
• 4.1 问题描述
• 4.2 序列匹配相关工作
• 4.2.1 Minkowski 距离
• 4.2.2 动态时间弯曲距离
• 4.3 FSM：快速子序列匹配算法
• 4.3.1 上下界策略
• 4.3.2 FSM 算法描述
• 4.4 实验
• 4.4.1 实验设置
• 4.4.2 实验结果
• 4.5 本章小结
• 第五章 数据流上改进的索引结构
• 5.1 问题描述
• 5.2 数据流索引相关工作
• 5.2.1 结点存储内容的改进
• 5.2.2 索引更新方式的改进
• 5.3 QDM-Tree 设计动机
• 5.4 QMBR 和QMBS 的比较
• 5.5 QDM-Tree 索引结构及相关算法
• 5.5.1 QDM-Tree 索引结构
• 5.5.2 插入算法
• 5.5.3 删除算法
• 5.5.4 查询算法
• 5.6 实验
• 5.6.1 实验设置
• 5.6.2 实验结果
• 5.7 本章小结
• 结束语
• 致谢
• 参考文献
• 作者在学期间取得的学术成果