摘要: 1．本文的创新点基于Bloom Filter技术，提出了一个新的概要数据结构—衰减性Bloom Filter (DBF)和一个动态更新DBF的有效算法。与以往的方法不同，DBF不需要额外的空间来保证滑动窗口的移动，而且也避免了计数器溢出的情况。另外，该方法只可能存在误是错误（False-positive error）而没有误否错误（False-negative error）。为了减低动态更新DBF的时间和空间复杂度，在DBF动态更新算法中引入了数据流分块和更新延迟技术，并且分析和证明了DBF处理每个元素的平均时间复杂度以及查询结果的误差概率最小上界。为了使得新算法更容易在实际应用中运用，从理论和实验两方面详细讨论了各个参数的设置，最后通过一系列在仿真数据流上的实验论证了在给定存储空间和滑动窗口大小情况下，该方法在误差概率和时间效率上都优越于前人的方法。2．实现方法通常情况下在滑动窗口上数据流副本检测的过程为：使用一个数据概要存储当前窗口中数据元素的成员关系，对于没一个新到来的数据元素，首先通过查询这个概要来判断该元素是否是副本，然后更新当前数据概要。因此，整个过程可分为查询操作和数据概要的更新操作，其中数据概要的更新算法决定了整个检测的时间成本和查询结果的精确度。以下是我们更新算法实现过程的高层次描述。首先我们引入了数据流的分块技术用于数据概要的更新，即通过数据块对数据概要的稀疏更新来来代替单个元素的频繁更新，以此来提高对数据流的处理速度和降低数据概要的存储空间。方法如下：我们将数据流划分成多个大小相等的不重叠的数据块。为了限定块的大小，我们引入了一个门限值T（T是整数且W>>T>0）对每个数据块按照0, 1, 2, …进行编号，其中编号越小的块所包含的数据元素越老。为表达方便，我们假定窗口大小W和块的大小T都为2的指数，那么当数据流中所见元素的个数超过W时，当前滑动窗口所涵盖的数据块个数在W/T和W/T+1之间。在任何时间点上，根据T和W的大小，以及当前所见数据流中的元素的个数，我们分配给每个数据块以下5种状态中之一。过期状态（Expired）：数据块中的所有元素（按照到达时间顺序）都比最新的W个元素老。处于销毁状态(Under destruction (UD))：数据块中存在部分元素比最新的W个元素老，且剩余的元素却属于当前最新的的W个元素。活动状态(Active):：数据块中所有元素属于当前最新的的W个元素。处于构造状态(Under construction (UC))：数据块中存在部分元素属于当前最新的的W个元素, 且剩余的元素还没有到达，即不可见。非活动状态(Inactive):：数据块中所有元素都还没有到达。每个数据块都要按照顺序经历非活动、处于构造、活动、处于销毁、过期状态。我们对每个数据块的处理过程如下：对于每一个新到达的元素，如果当前存在一个处于构造状态的数据块，那么将该元素插入该块中；否则，创建一个处于构造状态的数据块并将新元素插入该快中。当处于构造状态的数据块的状态中的元素个数达到T时，我们将其状态改变为活动状态并且（如果当前存在一个处于销毁状态的数据块）修改处于销毁状态的数据块的状态为过期。同时，当活动状态中存在数据元素比最新的W个元素老，我们标记该块为销毁状态。我们将一个数据块的从处于构造状态到活动状态称之为块的构造时间段。每个块的构造时间段涵盖T个元素。尽管上述处理数据块的过程比较复杂，但是实际上我们只需要处理当前滑动窗口中的数据块，即处于构造的数据块、活动的数据块和处于销毁的数据块，因为非活动的数据块和过期数据块对我们所要解决问题的结果不产生任何影响。3．结论及未来待解决的问题本文在滑动窗口上对数据流副本检测提出了一个新的数据结构—衰减性Bloom filter和一个简单而有效的动态更新算法。DBF能够避免计数器溢出同时保证了当滑动窗口移动时过期元素的删除。另外，它不需要像计数型Bloom filter那样需要额外的存储空间保存当前窗口中元素的到达顺序，因而节省了大量的存储空间。基于DBF，我们的更新算法通过将数据流划分成数据块并处理这些数据块来代替单个数据元素。仿真数据流上实验的结果已经证明了理论分析的有效性和该方法在时间和精确性方面的优越性。为达到我们的最终目标建立一个适用于高速数据流的数据流管理系统，还有大量的问题需要深入探讨和研究。如：(1) 数据流中不同的元素可能有着不同的初始剩余生命值。在实际中如何根据应用需要来定义不同数据元素的初始剩余生命值并进行有效的维护和副本检测，是一项很具挑战性的工作，需要进一步深入研究和探讨。(2) 分布式数据流应用正在日益普及，设计适用于分布式数据流应用的算法主要挑战是如何使网络的传输量最小化，本文提出的概要还不能满足这样的要求。如何改进本文提出的数据流中的概要结构以进一步提高算法的效率和扩展性也是我们今后考虑的重点。4．实用价值或应用前景目前，数据流在线监控已经成为数据流管理系统内的一个重要问题。其中挖掘和检测数据流中重复的元素（副本检测）是当前在线实时监控的一个热点问题，并且有着广泛的应用领域。如，最近Metally等人(2005)提出了在网络点击数据流上的副本检测的方法。在一个网络广告运用场景下，广告商按照广告的点击率付给出版商费用（点击率越高，费用越高，反之，越少）。但是，这里存在一个问题：出版商可能在利益的驱动下不实地增大广告的点击数量。因此，作为第三方的广告监督机构必须能够通过检测点击ID发现这些虚假的点击(以便维护广告商的利益)。每个点击ID是由用户ID和广告ID来唯一标识。当开始计算广告出版商的佣金时，广告监督机构通常运行查询算法来捕获在一段时间内的重复点击。URL Crawling【Heydon等99】【Border等03】作为数据流副本检测的另一个网络监控应用，搜索引擎通常需要从网络里捕获新的网页来扩大他们的网页集合。在给定一个网页地址（这个地址通常是从捕获的网页中提取出来的），搜索引擎必须去探查它的档案文件来确定该地址是否已经存在与他们的网页集合中以避免网页的重复。另外，副本检测也能用于查询不同的IP地址的，在一个网络监控和统计下，了解网络的通信量以及识别网络中的用户通常情况下是很重要的【Cisco02】。例如：下面的查询结果可能对网络监控者很重要：在过去的十二小时内那些用户在网络上？他们访问了那些资源等？因为这些答案有助于分析用户的信息，兴趣和网络流量。