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

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

关键词： 数据流，重复数据检测， Bloom Filter，滑动窗口
I
ABSTRACT
Data streams is a widely existing data form, such as stock information data
analysis in financial markets、data transmission in network, call records data in
telecommunications department、data in web click and so on. Due to its limitless、
real-time and high-speed etc. characteristics, it brings a great challenge to the data
streams analysis and data mining. Especially, the repetitive data on data streams,
the incorrect repetitive data caused by software and hardware failure and topology
structure, caused a great deal of influence in data streams-associated analysis、
correlational analysis and statistical analysis. Therefore, this paper focuses on the
repetitive data detection technology in data streams.
Firstly, this paper introduces some related work which includes data s