英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

针对分布数据流的有效多重过滤算法的研究

摘要:本文研究了物理性分散分布的数据流重复过滤的问题，为实时监控应用提供了干净的数据。现有的方法只针对局部冗余数据过滤每一个数据流，其在空间和时间上的成本消耗并不适用于高速数据流。基于空间/时间高效的数据结构布隆滤波器,我们提出了一种新的局部滤波算法来有效地过滤局部的重复数据,然后扩展到之前从未被解决的全局重复数据过滤的问题上。为了适应全局重复过滤与局部过滤不同的额外通信开销，我们基于布隆滤波器的分配提出了及时获取和延时获取的方法。理论分析和实验结果表明，我们的解决方案可以有效地过滤局部和全局的重复数据流，并且当参数设置正确合理的情况下，误差也足够小。

关键词:重复项目；分布式数据流；布隆滤波器

I简介

新兴的大型监控应用程序需要连续跟踪查询物理式分布的数据流信息。在大多数的分布式数据流的应用中，其中的一个主要特征就是相同的“事件”可能会在多个位置上被观察多次[1]。在传感器网络中，多个传感器的覆盖范围可能会因为全方位的监控而产生数据重叠，从而一个事件可能会被多个传感器观察监测。在无线射频识别数据流中，一个事件被重复观测是很常见的，一是标签会在一个阅读器的读写区内被多次读取，二是一个标签在多个阅读器重叠的部分也会被多个阅读器多次读取数据[2]。在IP网络中，由于TCP的重发机制，数据包将会被多次发送，每一份数据包都可以被任意的路由器在其路由路径上获取。

在这篇文章中，我们研究了分布式数据流重复过滤的问题。我们将问题具象化后，将其分成两种类型，局部和全局数据流重复。基于在空间/时间效率的数据结构布隆滤波器，我们针对局部和全局的冗余数据流过滤提出了有效的算法。更具体地说，我们的方案概括如下。

·基于界标窗口模型的重复过滤算法。将布隆滤波器应用于滑动窗口并不实际，因为布隆滤波器本身不能记录每一个元素的顺序。界标窗口是另一种常用的窗口模型，它可以自然地应用于布隆滤波器。

·有效过滤局部重复数据流。在每个远程站点的范围内，我们提出了一个原始的方法来重复过滤数据。由于Bloom Filter的过滤能力，相对于DTF滤波器[6](离散傅里叶变换滤波器)的方法，我们的方法获得了更大的空间和时间上的改进，同时当参数设置正确时，引入的错误率在可接受的范围。

·有效过滤全局重复数据流。DTF滤波器的方法不能过滤全局重复数据流。通过布隆滤波器的分配，我们的方法保存了在每一个远程站点的所有数据流的全局数据信息，从而可以过滤局部和全局的重复数据流。

接下来，论文的其他部分是按如下结构组织的。在第二节，我们回顾之前已完成的与重复过滤相关的工作。在第三节，介绍了一些相关的预备知识。在第四节，描述了针对局部冗余数据流的有效局部滤波算法。第五节，将该算法扩展到全局过滤，使其它可以有效地过滤局部和全局的冗余数据。在第六节，在现实世界网络模拟数据流的基础上，我们给出实验结果。第七节，得出结论性发言。

II相关工作

一些常用的混合式查询运算器对重复很敏感，例如求和，计数。对包含重复数据的查询可能导致错误的查询结果。一些论文中阐述了可通过扩展现有的一些方法支持恢复冗余数据集合[1]。现有的针对分布式数据流的过滤方法[3,4,5]主要集中讨论如何在整体误差符合标准要求的情况下，合理的调整远程点集使其在查询的误差允许范围，降低通信成本。

上述的这些方法从来没有考虑过重复过滤，但重复过滤一般可以运用于分布式数据流的任何查询的的预处理阶段。依据我们已经了解的，只有夏天等人[ 6 ]发表过针对分布式数据流的重复过滤问题，他们采用的DTF滤波器的方法，针对每个远程点使用二叉树原理，将每个元素的ID和时间戳分别设为索引关键字。然而，这种做法仍然存在以下两点不足之处。

·DTF滤波器只适用于滑动窗口应足够小的情况，因为每个元素的存储成本还需要加上元素实际的尺寸和元素的指针，因此它几乎不能运用在高速数据流的处理上，其主要的复杂度是算法所占空间的复杂度[7]。

·在DTF滤波器中，只能过滤局部冗余数据。一个站点绝对不能过滤在其

它站点中出现过的元素，除非这个元素曾经在这个站点中出现过。

III 准备工作

1. 问题定义

如图1中所示，存在有K个远程站点SK_i（i=1...K），和一个协调器站点SK₀，它们均分别包含有一个布隆滤波器的结构BF_i。每一个SK_i分别接收一条无界的数据流S_i（i=1...K），每一条还有冗余元素的数据流S_i经过BF_i进行过滤后，将“干净”的数据或者经查询后的结果在使用BFI，过滤器的重复元素然后把“干净”的数存在据或查询“干净”数据后的结果传送至协调器站点SK₀ 。每一个SK_i站点只与SK₀站点间进行通信。在数据流S_i中的每一个元素的关键值K_i,j(i=1...K)（i代表每个远程点的数量，j代表在数据流S_i中每个元素的局部时间戳）属于一个整数的集合[U]={0...U-1}。

图1 针对分布式数据流的重复过滤

·定义一：在站点i的局部冗余数据

针对每一项属于数据流S_i中的K_i,j(i=1...K)，如果存在一项属于数据流S_i中的K_i,j，使得K_i,jlsquo;=K_i,j，并同时满足jrsquo;ge;j,那么K_i,jlsquo;是站点i处的局部冗余数据。

·定义二：在站点i的全局冗余数据

针对每一项属于数据流S_i中的K_i,j(i=1...K)，如果存在一项属于数据流Srsquo;_i中的K_{irsquo;,jrsquo;},使得K_{irsquo;,jrsquo;}=K_i,j（jrsquo;ge;j），并且同时满足K_{irsquo;,jrsquo;}不是站点irsquo;范围内的局部冗余数据，那么K_{irsquo;,jrsquo;}站点i范围内的全局冗余数据。

举例说明。我们通过图2来举例说明以上的两点定义。在远程站点1中，第三个元素的关键值是“1”（我们在图二中利用直观的顺序来代替时间戳），它是一种局部冗余数据，因为它与远程站点1的第一个元素拥有相同的关键值，并且它的时间戳的值很大，所以相对于第一个元素而言，第三个元素是局部冗余数据。第五个元素“5”在远程站点1中是一个全局冗余数据。因为它拥有与远程站点2中相同的关键值，而且第五个元素的时间戳值大，并且对于站点1来说，第五个元素不是局部冗余数据，所以它是全局冗余数据。

图2 举例说明局部冗余和全局冗余

B：数据流

在文献[7]中有很多针对数据流处理的重要调查研究。在许多情况下，任意给定的时间段内的数据流只有部分的数据会被抽取，会被引用到窗口模型，其中有两类窗口模型被频繁地应用。

·滑动窗口。只有一部分固定数量的元素被处理。随着数据连续不断的到来，那些过期的元素将会被持续不断地驱逐出窗。

·界标窗口。界标窗口认为数据流被分解的那部分元素，就是被界标分离的。当数据流中有新的元素到来时，已经存在在窗口中的元素均不会被驱逐。

C：布隆滤波器

布隆滤波器[8]是一种节省空间的随机数据结构，布隆滤波器被用来近似的表示一组数据的检测和查询，布隆滤波器BF是由Burton H.Bloom 在1970年首次提出的。

标准的布隆滤波器是一个比特数组，所有的布隆滤波器中的数组最初设置填充的都是0。为了表示一个大的数据集合S={x₁，...,x_n}，对于每个x_i属于S集合，布隆滤波器使用K个独立的哈希函数{h₁(x_i),...,h_k(x_i)}映射到比特数组的K个不同位置，并置1。要检查一个新来的元素是否存在于数据流S中，我们可以检查所有的哈希函数h_i(y)是否全部被置为1。

布隆滤波器可能会产生假阳性误判，当参数设置正确时，假阳性误判的概率将被降低到一定的数量[9]。布隆滤波器不会产生假阴性误判。

IV过滤局部冗余数据

在数据流中过滤冗余数据的原始方法只能在局部过滤重复的元素。每个站点都使用它自己的布隆滤波器来检查新来的元素是否之前曾出现过，然后再更新已有布隆滤波器中的数据。在协调器站点SK₀中，只接收来自SK_i的元素，然后由用户来查询数据的答案。

在每个远程站点的数据处理中，我们设计了一种局部滤波的算法1。在整个的过滤过程中，远程站点通过布隆滤波器简单的查找已经接收到的元素，然后将那些经处理过后没有冗余元素的数据发送至协调器站点SK₀处。

局部过滤是一种有效节省空间和时间占用的方法，在其他参数设置正确的情况下，引入了小概率的假阳性误判，这是可以接受的［９］。因为布隆滤波器的的假阴性误判率是零，局部滤波器可以滤除所有的局部冗余数据，但是却不能过滤掉任何全局的冗余数据，因为局部过滤器无法捕捉到之前接收过的全局历史数据流。

V局部冗余和全局冗余数据的过滤

为了过滤掉局部冗余和全局冗余数据，每一个远程站点都储存有一部分之前的历史数据流Ｓ_０＝Ｓ_１Ｓ_２。。。Ｓ_ｋ。因为每个远程站点只能与协调站点进行通信传输数据，远程站点必须通过协调站点才能共享全局的历史数据。我们　在第四部分通过添加两个关于布隆滤波器的分配的过程，将局部滤波扩展延伸至全局滤波。这两个补充的过程如下。

·定义3：布隆滤波器的更新。当一个远程站点SK_i接收到一个非重复的元素时，除了发送元素单元至协调站点SK₀，同时它将把它已经更新过后的局部滤波器BF_i发送至协调站点SK₀。这是布隆滤波器的更新过程。

·定义4：布隆滤波器的散射。当从远程站点SK_i处接收到经更新后的布隆滤波器后，协调站点SK₀第一时间接收此时的BF_i和BF_０，得到新的BF_０lsquo;，然后将这个新的BF_０lsquo;发散至一些其他远程站点。这是布隆滤波器的散射过程。

Ａ．布隆滤波器的更新

要使布隆滤波器保持更新，最直接的方法是当远程站点之前从未检测过的元素出现时，刺激从该远程站点到协调站点之间的布隆滤波器进行更新。但是这种方法是不太实际的，因为额外的通信成本太高，更糟糕的是，当系统只是处于安装阶段时，几乎所有的元素都是新的元素，这样一来，通信成本将会大大增高，所以对于实际应用来说不合理。

不同于把每一次的更新都发送给协调站点，在接下来展示的算法２中，我们推迟了从远程站点发送出来的更新数据。为了减少额外的通信成本，远程站点记录不同从上一次更新发送过的元素，当统计的不同元素的数量超过规定的阈值时，才使布隆滤波器更新后再次发送时。

当协调员站点SK₀接收到从远程站点SK_i处更新过来的布隆滤波器，然后将它之前的滤波器与现在新接收到滤波器进行合并后来作为更新的全局布隆滤波器。（“合并”操作就像逻辑里的“或”功能，比特与比特构成两个比特串，就像图三中显示的“Ｕ”），这个新的全局布隆滤波器会被分散到一些其他远程站点。在下一节中，我们将描述了运用不同策略进行的布隆滤波器的散射过程。

Ｂ．布隆滤波器的散射

　·及时散射。协调站点通过在每个远程站点除了图三（ａ）中显示的更新数据来实时广播更新布隆滤波器，确保了所有的远程站点获得最新更新的布隆滤波器。

　·延时散射。虽然及时散射确保了远程站点拥有最新的全局布隆滤波器，但是用在广播上的额外通信的容量占用引入对于分布式的数据流应用来说是不可以被接受的。

　相反，我们可以对采用延时散射（如图3（ｂ）所示）。协调站点SK₀不会播送。每次当一个远程站点输送更新后的布隆滤波器至SK₀时，它都会从SK₀处得到当前全局布隆滤波器作为回馈。

图3 多种布隆滤波器的散射方案

VI实验

本实验的目的是为了评估过滤的速率和对针对现实世界模拟的网络流数据在该方案下的错误率的检测。所有的实验都是在设备环境奔腾4PC(2.8G处理器，1GB的内存和Windows XP操作系统等)。网络数据流文件是从两个

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[150294]，资料为PDF文档或Word文档，PDF文档可免费转换为Word