数据流重复数据检测方法的研究

论文摘要

流数据是一种广泛存在的数据形式,如金融市场证券信息分析数据、网络传输数据、电信部门的通话记录数据、Web点击数据等。流数据由于其无限性、实时性、高速性等特点,给数据流分析和挖掘带来极大挑战。特别是,数据流上的数据重复性,即由于软硬件故障、拓扑结构等原因产生的非正确重复性数据,对于数据流关联分析、相关性分析、统计分析等带来极大影响。为此,本文重点研究了数据流上的重复数据检测技术。本文首先介绍了一些相关工作,包括数据流及其模型,概要技术和一些重复检测技术。然后指出了SBF等方法可能无法降低误判率和浪费系统资源等不足。本文的重复检测技术主要面向高速、实时、海量、变化的流数据,要求检测方法具有在线处理和实时响应特性。为此,本文提出一种基于Bloom Filter的自适应重复检测方法ABF(Adaptive Bloom Filter),主要研究内容有:(1)提出一种基于Bloom Filter的错误约束下的重复检测方法。方法利用了滑动窗口数据概要结构,同时为了适应重复变化,对窗口进行分块。给出了在用户指定误判率约束条件下的数据分块Bloom Filter长度确定理论。该方法可以在保证用户误判率的同时,简化数据概要的更新操作,加快数据重复检测的速度。(2)为了能够反映数据重复变化,提出一种自适应窗口滑动策略。能根据检测到重复数据的间隔自动改变未来窗口的大小和滑动步长,从而提高检测的准确率和效率。通过分析我们的方法的误差只能产生假阳性,而没有假阴性。(3)基于ABF方法,本文进一步提出一种面向分布式数据流环境下的重复检测方法。该方法采用在其它机器上保存一个BF副本,将非重复数据所映射的位传递到其它机器的副本上,再利用这个副本与副本所在机器窗口内的BF进行对比,然后检测出重复数据。其可以保证与集中式检测相同的误检率,并且具有较高的空间使用率和较低的网络通信代价。理论分析和实验结果表明,本文提出的数据流重复数据检测方法具有较高的精度和较低的时间、空间复杂度,更加适用于数据流的应用场景。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 引言
• 1.2 课题研究背景
• 1.3 本文研究工作
• 1.4 论文组织结构
• 第2章 相关工作
• 2.1 数据流
• 2.2 数据流管理系统
• 2.2.1 数据流管理系统体系结构
• 2.2.2 数据流管理系统实例
• 2.3 窗口模型
• 2.3.1 快照式窗口
• 2.3.2 界标式窗口
• 2.3.3 滑动式窗口
• 2.3.4 跳动窗口
• 2.4 概要技术
• 2.4.1 直方图方法
• 2.4.2 抽样方法
• 2.4.3 小波方法
• 2.4.4 哈希方法
• 2.5 重复检测
• 2.5.1 Bloom Filter 的介绍
• 2.5.2 现有重复数据检测方法的分析
• 2.6 本章小结
• 第3章 基于 Bloom Filter 的自适应重复检测方法
• 3.1 基本概念与定义
• 3.2 滑动窗口分块
• 3.2.1 问题提出
• 3.2.2 解决方法
• 3.3 数据分块中Bloom Filter 长度的确定
• 3.4 自适应滑动策略
• 3.4.1 基本思想
• 3.4.2 处理实例
• 3.4.3 相关算法
• 3.4.4 Adaptive Bloom Filter 方法的误差分析
• 3.4.5 空间和时间复杂度
• 3.5 本章小结
• 第4章 分布式系统上重复数据的检测
• 4.1 问题提出
• 4.2 解决方案
• 4.3 错误率分析
• 4.4 相关算法
• 4.5 本章小结
• 第5章 实验及结果分析
• 5.1 参数设置
• 5.1.1 数据流设置
• 5.1.2 k、T 等参数设置
• 5.2 错误率分析
• 5.3 时间分析
• 5.4 本章小结
• 第6章 结论与展望
• 致谢
• 参考文献
• 攻读学位期间发表的学术论文及参加科研情况