（计算机应用技术专业论文）基于bloom+filter技术的若干数据流处理算法.pdf

摘要 摘要 数据流模型的出现对数据的管理与分析提出了新的要求，如直接反映数据的 本来面目、可以处理连续查询、能够处理异种数据、快速响应用户查询等，其本 质是对数据流的管理和分析。因此，必须进行数据流管理与分析新技术的研究， 并且已经成为当前的一个研究热点。典型的数据流管理与分析包括数据流采集与 预处理、数据的特征抽取、数据聚集等基本连续查询的分析与执行、相关性检测 或预测与分类等复杂的分析操作。研究数据流相关技术不仅有重要的学术价值， 而且在传感器网络、气象监测与分析、移动物体位置跟踪、股票分析、邮件过滤、 网络监控与安全等领域有着巨大的应用前景。本文对数据流在线分析的若干关键 问题进行了深入探索，主要有以下内容： ( 1 ) 致力于滑动窗口上副本检测的研究，提出了一个基于计数型b l o o mf i l t e r 的新的数据概要d e c a y i n gb l o o mf i l t e r ( d b f ) 和一个有效的概要动态更新算法。 d b f 能够通过保存元素的剩余寿命值来维护窗口的移动，即，删除过期的元素 来保存新到达的元素。为了提高概要的更新的速度和降低存储空间，我们在更新 算法中引入了分块和延迟技术，已知空间g 比特位和滑动窗口大小巩d b f 更 新的平均时间复杂度为d ( g 矿) 。通过深入分析指出该方法只存在误是错误而 没有误否错误以及误是错误概率的最小上界。 ( 2 ) 致力于数据流历史数据的近似聚集查询的研究；基于b l o o mf i l t e r 提出 了新的概要存储模型m u l t i b l o o mf i l t e r s ( m b f ) 。m b f 能够有效地支持时间范 围内的历史数据元素的成员关系查询和频率查询，同时，m b f 具有很大的灵活 性，它能够支持对较新的历史数据细的时间粒度的查询；而且可以通过对较久远 的m b f 压缩以节约存储空间，同时能够支持相对较近的数据粗的时间粒度的查 询。 ( 3 ) 数据流中任意子集的副本无效并且时间衰减的和是一个用于分布式流 下的各种分析的重要聚集。我们致力于此问题并引入了新的解决方法，该方法不 仅能够检测数据流中副本而且能够根据用户定义的衰减函数来动态维持数据流 中不同元素的衰减权值。另外当查询数据流的任意子集的衰减的和时，能够返回 一个具有误差保证的估计值。 综上所述，本文针对数据流现有在线分析中存在的三类问题，分别提出了从 问题定义、概要数据结构到具体算法的完整方案。理论分析和实验结果表明，与 已有的研究成果相比，本文给出的解决方法具有较高的精度和较低的时间、空间 复杂度，更加适用于数据流的应用场景。 关键词：数据流；概要数据结构；b l o o mf i l t e r 技术；副本检测；滑动窗口；历 摘要 史数据：近似聚集查询；时间衰减函数；衰减聚集和 i i a b s t r a c t m a i n t a i nd e c a y e d w e i g h to fa l ld i s t i n c te l e m e n t si i lt h es t r e 锄a c c o r d m gt o a u s e r - s p e c i f i e dd e c a yf h n c t i o n f o raq u e r ) rf o r t h ec u l l r e n td e c a y e ds u m o fas u b s e ti n t h es t r e a m ，t d b fc a i lp r o v i d cag o o de s t i m a t i o n i i lo u rt h e o r e t i c a la n a l y s i s ，a n a p p r o x i m a t eg u a m n t e eh a sb e e ng i v e nf o rt i l ee r r o ro f t h ee s t i m a t i o n i na d d i t i o n ，龇 e x p e r i m e n t a lr e s u l t so ns y n m e t i cs t r e 锄v a l i i i a t eo u rt l l e o r e t i c a la n a l y s i s i ns u m m a 吼t h i st h e s i si sf o c u s e do nt l l r e eb a s i cp r o b l e m si no n l i n em o n i t o r i n g a n da n a l y s i so fd a t as t r e 锄s i tp r o p o s e sam o r eg e n e r a lm e m o df r o mp r o b l e m d e f l n i t i o na n da b s t r a c td a t as 缸u c t u r ed e s i g i lt oa l g o r i t l l md e v e l o p m e n t f o ro n l i n e m o n i t o r i n ga n da n da n a l y s i so fd a t as t r e 锄s t h e o r e t i c a la n a l y s i s a n de x p e r i m e n t a l r e s u l t ss h o wt h a to u ra l g o r i t h m sc a na c m e v eah i g h e rp r e c i s i o nw i t h1 e s s sp a c ea n d t i m ec o m p l e x i t ya sc o m p a r e d 、v i t ht h ee x i s t i n gm e t h o d s a st h er e s u l t ，t l l ep r o p o s e d a l g o r i 岫i ss u i t a b l ef o rm a n ys t r e a ms c e n a r i o s k e yw o r d s ：d a t as t r e a m s ；s y r l o p s i s d a t as t u c t u r e ；b l o o mf i l t e r s ； d u p l i c a t e d e t e c t i o n ；s l i d i n gw i n d o w s ；h i s t o r i c a ld a t a ；a p p r o x i m a t ea g g r e g a t eq u e r i e s ； t i m e d e c a y i n gf u n c t i o n ；d e c a y i n gs u m 中国科学技术大学学位论文原创i 生和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：孳丝蚕 矿咯年厂月舻日 第l 章绪论 1 1引言 第1 章绪论 在2 0 世纪末，随着信息技术的飞速发展，数据流( d a t as t r e 锄) 的应用模型广 泛出现在众多应用领域，如：传感器网络、网络监控、事务日志、电信部门的通 话记录数据、金融市场内股票交易所的股票价格信息数据等。数据流不同于存储 在磁盘上的传统关系数据，而是以实时、快速、无限、有序、连续的流的形式存 在( 顺序由到达时间隐含地表示或显式地由时间戳指定) 。下面列举几个这些方 面的应用。 ( 1 ) 传感器网络 传感器网络被用在地理监控( 地表的温度、湿度等) 、公路交通状况监控、移 动追踪、医疗设备监控、制造流程监控等。这些应用包含复杂的过滤，要求能够 即使的发现记录中不正常的模式。同时对多个数据流处理时，要求能够进行聚集 和多个数据流的连接操作。传感器上的数据查询可能要求访问历史数据。典型的 查询包括： a ) 当某个区域的多个传感器产生的数据同时超过给定门限值时处理器能够 激发一个触发器报告异常。 b ) 在天气地图上绘出温度轮廓：对多个产生温度数据的流进行连接操作：对 温度数据和静态的地理数据( 经纬度) 进行连接操作。把所有温度相同的点能够连 接起来。 c ) 发电站接收并分析每个城市最近的电力使用情况。从而当必要时能够调 整发电量 1 。 ( 2 ) 网络流量分析 现在已经存在对互联网流量进行实时分析的系统 2 。正如在传感器网络中， 要求能够对多个数据源的数据进行连接操作、数据包监控、数据包过滤和检测非 正常模式( 网络拥挤或拒绝服务) 。能够支持历史查询和在线查询，例如流量状况 和对应于某种已知的事件的模式。其他查询包括监控对流行的u i 也的访问情况 和发现占据大量带宽的用户。这些应用非常重要，因为已有研究工作表明：网络 流量模式服从p o w e rl a wd i s t r i b u t i o n ，即小部分用户占据了很大比例的带宽。以 下是典型的查询类型： a ) 流量矩阵：监控每个源一目的节点对使用的带宽，并能够对不同的正地 址、子网掩码、协议类型进行g r o u pb y 操作。并且，能够把每个数据流分成 第l 章绪论 1 1 2 数据流管理系统与传统数据库管理系统的对比 自2 0 0 0 年以来，数据流管理与分析是学术界和工业界所共同关注的热点问 题。管理和处理数据流的系统称为数据流系统。它涉及到实时数据库、主存数据 库、主动数据库、大型数据库查询的近似解答、在线数据挖掘、联机分析处理等 许多活跃的研究领域，具有重要的理论价值与实用价值。 传统的数据库管理系统旨在处理持久、稳定的数据，强调维护数据的完整性、 一致性，其性能目标是以较低的代价获得较高的系统吞吐量，其设计目标是维护 数据的绝对正确性、提供友好的用户接口等。这种数据库管理系统对于传统的事 务型应用是有效的、成功的，然而它不适合于处理无限数据的、快速的、实时的 应用，关键在于传统的数据库管理系统通常不考虑与事务相关联的时间和空间限 制，其调度与处理决策不考虑数据的各种时间特性，其系统的设计指标并不强调 实时性和查询服务质量的自适应性，而实时性和自适应性恰恰是数据流应用所必 须的。与传统d b m s 一切为了保证结果的绝对正确性相反，d s m s 更看重自适 应性，允许向用户提供近似查询结果。目前还没有d b m s 提供内建的功能支持 近似查询回答。d b m s 与d s m s 的对比如表1 1 。 表1 1d b m s 与d s m s 的对比 比较内容数据库管理系统( d b m s )数据流管理系统( d s m s ) 数据关系持久稳固的关系瞬时的数据流 查询方式 一次查询( o n e t i m eq u e r i e s ) 长时间连续查询( c o n t i n u o u s q u e r i e s ) 访问方式随机访问 顺序存取 存储空间 极大的磁盘存储有限的主存空间 数据状态仅表示当前的事件状态历史到达顺序是关键性特征 存储方式被动的储藏库主动存储 数据率相对低的更新速率可能是多路g b 级到达速率 响应时间 不具有实时服务功能实时服务是必要功能 精确度精确的数据数据可能是陈旧或不精确的 系统特征查询计划静态生成不可预知变化的数据抵达 方式和特征 d s m s 与传统d b m s 相比，新颖性主要表现在三个方面： ( 1 ) 语义( s e m a n t i c s ) ：流按时间顺序输入，查询结果以流形式输出。 ( 2 ) 状态( s t a t e ) ：不能存储无终止的流，某些操作需要历史记录。 ( 3 ) 性能( p e r f o m a n c e ) ：自适应性( a d a p t i v i t y ) ，速率可变性( 、，a r i a b i l i t ) r ) ，不 第l 章绪论 精确性( i m p r e c i s i o n ) ， 数据流和连续查询的特性要求d s m s 必须具备下述功能： ( 1 ) 数据模式和查询语义必须允许基于顺序和基于时间的操作，比如支持在 5 分钟尺寸大小的滑动窗口上的查询。 ( 2 ) 长时间运行的查询在执行生命期中可能会遇到系统条件的变化，例如流 速率的变化，需要设计具有自适应性的查询计划和调度策略。为即时准 确地响应用户查询和确保可伸缩性，需要通过服务质量的检测指导系统 调度和负载均衡的策略。 ( 3 ) 在线数据流算法受到计算资源和扫描次数等方面的限制，不能存储全部 的流数据，这意味着需要使用近似概要结构，文献中称为大纲 ( s y n o p s i s ) 3 或摘要( d i g e s t s ) 4 ，作用在概要上的查询可能会返回不精 确的结果。 ( 4 ) 数据流查询计划需支持非块式操作( n o n - b l o c k i n g ) ，即在产生结果之前不 必消耗完全部输入的数据。同时允许调度多个连续查询以共享某些操作， 这种并发执行的方式是提高查询响应时间的有效途径。 1 2 基本概念 为了便于描述，本节给出后面章节中论述所必须的有关数据流管理及分析的 基本术语的含义，包括窗口模型、概要数据结构等。我们假设大小为的数据 流描述为由连续的数据元素e l ，p 2 ，p j v 组成，按下标递增的顺序依次到达，数 据元素p ，可能包含多维属性。当此数据流无限时，变为无穷大。 1 2 1 窗口模型 数据流具有着连续性和无限性的特点，数据向未来的时间方向无限延展和向 过去的时间方向无限流逝，因此，数据流系统在大多数情况下无法处理全部的数 据，例如，当进行连接和聚集操作的过程中，不可能访问到已经过期的数据和尚 未到达的数据，而且当前保留的数据也受到存储空间等诸多方面的限制。为了适 应数据流的特点以及大多数实际应用的需要，在数据流系统中广泛使用了窗口技 术，连续地对数据流中的部分数据进行处理。窗口是对数据流上数据的区域性限 定，即针对数据流的无限性所作的处理，使查询对数据流所作的操作全部限定在 窗口范围之内。由于窗口中只包括数据流上的部分数据，查询处理得到的不是精 确的结果而是近似结果，因此，窗口技术也可以看作是一种近似查询技术。数据 流是由离散的数据元素所构成，因此，窗口的划分方式可以是基于时间也可以是 4 第1 章绪论 基于元素数量的，也就是说窗口的长度可以是时间单位也可以用元素数量来表 示。基于时间的窗口限定的是窗口内元组所跨越的时间长度，例如，窗口的长度 为8 秒即表示窗口内保存的是8 秒钟之内的全部元组；基于元素数量的窗口限定 的是窗口内元素的数量，例如，窗口的长度为8 0 个元素则表示窗口内保存的是 数据流上的8 0 个元组。一般的应用需要使用的窗口通常都是从当前时刻起到过 去某个时刻结束，即需要最近一段时问或一定数量的数据。 窗口根据它的移动方式可以分为以下三种： ( 1 ) 快照式( s n a p s h o t ) 窗口。快照窗口有固定的窗口的起始和结束点，并且 当窗口己经满足起始与结束的条件时一次性将结果输出； ( 2 ) 界标式( l a n d m a r k ) 窗口。界标窗口则只固定窗口的起始点，窗口的另一 端随着数据的不断到达而增长，不断地把得到的结果输出，但是，这种 窗口是不可以无限制的增长的，仍然要给它定义一个结束点，使窗口延 伸到这个点时结束查询； ( 3 ) 滑动式( s l i d i n g ) 窗口。滑动窗口对窗口的起始与结束都没有明确的定 义，定义的是窗口的长度，窗口保持一定的长度在流数据上进行滑动， 不断地把得到的结果输出，直至查询结束滑动窗口也可以定义一个结束 点，当窗口前端滑动到这个点时结束查询。 窗口除了具有以上这些特性之外，还有一个重要的属性就是跳数( h o p ) ，即 窗口移动的频率特性。跳数是窗口每次需要移动的长度，因为窗口中保存的是离 散的数据单元，因此窗口移动是跳跃式的。这个跳数同样有基于时间的和基于元 组的两种，分别对应于相应的窗口类型。例如，对于一个基于时间的1 0 秒钟长 度的滑动窗口，它的跳数为2 秒，则代表窗口每向前滑动秒钟就需要作一次处理， 基于元组数量的滑动窗口的跳数为元组的个数，其他特性与基于时间的窗口是 样的。 1 2 2 概要数据结构 图l 。l 给出了数据流处理模型，该模型需要在内存中维护一个概要数据结构。 数据流管理系统响应用户提交的d m l 语句，搜索数据存储媒介，返回查询结果。 因为数据流数据规模很大，如果数据以磁盘或者磁带为介质，因而执行查询操作 需要大量的i 幻交换，效率低下，不能适应实时系统的需求。相反，新的流数据处理 技术并不保存整个数据集，仅维护一个远小于其规模的概要数据结构，从而能够 常驻内存。流数据处理技术往往包含两部分算法，一部分监控流中的数据，当“看” 到一个新元素时，更新概要数据结构：另一部分响应用户查询请求，从概要数据结 构中获取近似查询结果。在许多数据流应用中，计算资源和通信资源是极为有限 第l 章绪论 的，为了及时地完成某些复杂的数据流处理，例如决策支持、查询优化等，用户 不得已需要接受近似的解答。因此，设计单遍扫描算法( o n e p a s sa l g o r i t h m ) ，实 时地给出近似查询结果是数据流模型下数据处理的目标之一。近似算法的关键在 于设计一个远小于数据集规模的结构，从而可以在内存中处理数据。这种名为概 要数据结构( s y n o p s i sd a t as t m c t u r e ) 的规模至多应该是数据流规模的次线性函数。 允许得到近似结果的查询操作可以在概要上执行，而不必直接访问无限的流数 据。直方图、抽样、小波、哈希等都是非常有效的构造概要数据结构的方法。 d a t as t r e 锄 d m l q u e r yr e s u l t s y n o p s i sd a t as t r u c t u r e o n e - p a s sd a t ap r o c e s s i n ga l g o r i t h m s 图1 1 数据流处理模型 1 3 研究现状 最近几年，国内外的数据库研究人员已经对数据流管理闯题开展了大量的研 究工作。一方面，出现了很多数据流模型下的管理系统，即数据流管理系统( d a t a s t r e 锄m a n a g e m e n ts y s t e m ，简称d s m s ) ，包括斯坦福大学的s t r e a m 项目 5 、 加州大学b e r k e l e y 分校的t e l e g r a p h c q 项目 6 ，7 、布朗大学和麻省理工学院合 作的a u r o r a 项目 8 等等，这些系统针对具体行业背景，给出较全面的数据管理 解决方案。这方面的研究工作包括设计新型的系统架构、查询语言、资源分配、 查询优化等等。另一方面，基于数据流模型的算法也得到了广泛的研究，包括副 本检测 9 ，l o 、近似聚集查询 1 l ，1 2 、密度估计 1 3 等等。上述数据流模型算 法研究的核心是概要数据结构的设计，并且数据流算法可以不依赖任何系统独立 运行，也可以嵌在d s m s 中为查询优化服务。文献 1 ，1 4 ，1 5 从不同角度综述了 数据流的研究进展。文献 1 侧重于如何构建d s m s 。文献 1 4 介绍了几种生成 概要数据结构的方法。文献 1 5 3 介绍了流数据模型下查询和挖掘的一些算法。 1 3 1 系统研究 现在有很多数据流管理系统被开发出来。t a p e s 仃y 系统 1 6 能够对只增数据 库( 如电子邮件、布告栏消息) 进行基于内容的过滤。a i e r t 系统 1 7 用了事件一条 件一反应( e v e n t c o n d i t i o n a c t i o n ) 机制对传统的s q l 数据库进行操作。x y l e m e 系 6 第l 章绪论 统 1 8 是一个基于内容的过滤系统，具有很高的吞吐率，它同时支持一个受限制 的查询语言。t a n g r 锄系统 1 9 ，2 0 利用数据流处理技术去分析大规模储存数据。 t u k w i l a 系统 2 1 具有适应性查询处理技术，从而对自治数据源( a u t o n o m o u sd a t a s o u r c e ) 进行动态数据集成。 o p e n c q 系统 2 2 和n i a g a r a c q 系统 2 3 支持监视广域网中永久数据集合 ( 例如因特网上面的网站) 的连续查询。o p e n c q 系统使用增量视图维护技术来处 理查询：n i a g a r a c q 系统着眼于系统的扩展性，它采用查询分组技术提高查询处 理性能。t e l e g r a p h 系统 2 4 ，2 5 ，2 6 的目的是建立一个适应性的流处理系统，主 要面向传感器网络和因特网。它采用一个适应性查询引擎( 基于e d d y 技术 2 4 ) ， 即使在一个不稳定的环境中，仍能够具备很高的性能。 s t i 也a m 系统 2 7 是一个通用目的的数据流管理系统，它支持c q l 查询语 言 2 8 。s t r e a m 系统的特点在于它的内存管理技术和近似查询回答技术。 a u r o r a 系统 2 9 面向数据流监控应用，其查询处理架构和s t r e a m 系统很类似。 a u r o r a 项目的核心是创建一个查询计划来处理查询。一个计划就是一个包含许多 操作( 盒子) 和队列( 边) 的数据流程图，增加一个查询则扩大当前计划：删除一个 查询则缩减当前计划。为处理传感器网络而创建的数据流系统和上述系统均有所 不同，这些系统主要考虑的是如何降低传感器之间的通讯量、如何在不需要时关 闭传感器、以及其它类似的要延长传感器寿命的问题。代表性系统包括t i l l y d b 系统 3 0 和c o u g a r 系统 3 1 。 过滤和散布x m l 文档是一些消息发布机构的核心任务。x f i t i e r 系统 3 2 是 一个基于内容的过滤系统，能够利用连续查询技术高效处理x m l 文档。类似的， x p u s h 机器 3 3 和x s q 系统 3 4 也拥有快速过滤x m l 文档的算法。另外还有 一些针对网络数据包流的系统。t r i b e c a 系统 3 5 具备部分处理网络包数据流的 能力。i p s o f a c t o 系统 3 6 能够为交通聚集信息提供可视化功能，它还能够比 较不同时间序列的相关性。g i g a s c o p e 系统 3 7 是另外一个高性能的网络监控工 具，它支持一个s q l 查询接口。h a n c o c k 系统 3 8 能够分析电话呼叫记录。 1 3 2 算法研究 数据流上的算法研究常用的概要数据结构有： ( 1 ) 抽样( s a m p l i n g ) 方法 抽样方法也是生成概要数据结构的常用手段。它从数据集中抽取小部分数据 代表整个数据集，并根据该样本集合获得查询结果。抽样方法可以分成均匀抽样 ( u n i f o ms a m p l i n g ) 和偏倚抽样( b i a s e ds 锄p l i n g ) 两种。在均匀抽样方法中，数据 集中各元素以相同的概率被选取到样本集合中；而在偏倚抽样方法中，不同元素 第l 章绪论 1 4 主要研究工作和内容安排 本文主要研究了数据流分析技术中的聚集查询和副本检测技术，主要工作包括以 下几个方面： 1 研究了基于滑动窗口上的副本检测问题，提出了一个基于计数型b l o o m f i l t e r 提出了新的数据概要一d e c a y i n gb l o o mf i l t e r ( d b f ) 和一个有效的概要动态 更新算法。d b f 能够通过保存元素的剩余寿命值来维护窗口的移动，即，删除 过期的元素来保存新到达的元素。为了提高概要的更新的速度和降低存储空间， 我们在更新算法中引入了分块和延迟技术，已知空间g 比特位和滑动窗口大小 彬dbf更新的平均时间复杂度为o(厮)。通过深入分析指出该方法只存在误 是错误而没有误否错误以及误是错误概率的最小上界。 2 研究了数据流历史数据的近似聚集查询；基于b l o o m filter提出了新的概 要存储模型m u l t i b l o o mf i l t e r s ( m b f ) 。m b f 能够有效地支持时间范围内的历 史数据元素的成员关系查询和频率查询，同时，m b f 具有很大的灵活性，它能 够支持对较新的历史数据细的时间粒度的查询；而且可以通过对较久远的m b f 压 缩以节约存储空间，同时能够支持相对较近的数据粗的时间粒度的查询。 3 数据流中任意子集的副本无效并且时间衰减的和是一个用于分布式流下 的各种分析的重要聚集。我们致力于此问题并引入了新的解决方法，该方法不仅 能够检测数据流中副本而且能够根据用户定义的衰减函数来动态维持数据流中 不同元素的衰减权值。另外当查询数据流的任意子集的衰减的和时，能够返回一 个具有误差保证的估计值。 本文分为五大部分，第一部分对数据流的产生背景、特性、主要应用以及数 据流上研究的背景的进行了详细的叙述；第二部分阐述了数据流上的副本检测问 题，介绍了当前数据流各个模型下副本检测的方法，并且提出一种在滑动窗口上 副本检测的概要结构和一个动态更新算法，使之可以应用在分布不均衡的数据流 场景中，并用实验详细分析了该方法的性能：第三部分对数据流数据流历史数据 的近似聚集查询进行了研究，提出基于b l o o mf i l t e r 提出了新的概要存储模型 m u l t i b l o o mf i l t e r s ( m b f ) ：第四部分对分布式流下数据流中任意子集的副本无 效并且时间衰减的聚集和问题进行了描述，并提出了解决方法：第五部分总结本 文，并给出了一些相关的讨论和未来工作的展望：第六部分列出了本文所引用的 主要参考文献，最后对在硕士生学习科研及论文写作过程给我指导，帮助的导师， 同学表示感谢。 1 0 第2 章滑动窗口上数据流副本检测的有效算法 第2 章滑动窗口上数据流副本检测的有效算法 2 1 引言 目前，数据流在线监控已经成为数据流管理系统内的一个重要问题。其中挖 掘和检测数据流中重复的元素( 副本检测) 是当前在线实时监控的一个热点问题， 并且有着广泛的应用领域。如，最近m e t a l l y 等人 9 】提出了在网络点击数据流上 的副本检测的方法。在一个网络广告运用场景下，广告商按照广告的点击率付给 出版商费用( 点击率越高，费用越高，反之，越少) 。但是，这里存在一个问题： 出版商可能在利益的驱动下不实地增大广告的点击数量。因此，作为第三方的广 告监督机构必须能够通过检测点击i d 发现这些虚假的点击( 以便维护广告商的 利益) 。每个点击i d 是由用户i d 和广告i d 来唯一标识。当开始计算广告出版商 的佣金时，广告监督机构通常运行查询算法来捕获在一段时间内的重复点击。 u r lc r a w l i n g 5 7 】 5 8 】作为数据流副本检测的另一个网络监控应用，搜索引擎通 常需要从网络里捕获新的网页来扩大他们的网页集合。在给定一个网页地址( 这 个地址通常是从捕获的网页中提取出来的) ，搜索引擎必须去探查它的档案文件 来确定该地址是否已经存在于他们的网页集合中以避免网页的重复的提取。另 外，副本检测也可用于查询不同的i p 地址，在一个网络监控和统计下，了解网 络的通信量以及识别网络中的用户通常情况下是很重要的 5 9 】。例如：下面的查 询结果可能对网络监控者很重要：在过去的十二小时内那些用户在网络上? 他们 访问了那些资源等? 因为这些答案有助于分析用户的信息，兴趣和网络流量。 依赖于数据流的处理方式，数据流的副本检测主要被分为两种：( 1 ) 基于界 标窗口的副本检测。它检查从某个界标开始的所有副本，界标可能根据元素的个 个数或时间单元定义：( 2 ) 基于滑动窗口的副本检测。它检查目前数据流中最近形 个元素( 时间单元) 里的副本。 数据流中的元素通常是时间敏感的，即，数据流中距离当前较近的元素比距 离当前较远的元素重要。因此，提供最近元素的副本信息至关重要。另外，由于 数据流的无限性，我们不可能将缓存整个数据流的历史元素。因此，基于滑动窗 口上的数据流副本检测更具有实际应用意义。一个直观的数据流的副本检测方法 就是：首先利用缓存存储当前滑动窗口中的所有元素：当一个新的元素到达时， 我们将它与缓存中的所有元素进行比较，从而判断该元素是否是副本；当缓存饱 和时( 当前窗口移动) ，需要在将新到达的元素存储到缓存前将旧的元素删除。 这个方法的主要缺点就是：当滑动窗口大小为形时，我们需要对d ( 即个对 比来判断新到达的元素是否是副本。尽管为每个元素建立索引可以将每个元素搜 第2 章滑动窗口上数据流副本检测的有效算法 包括：误是错误( f a l s e p o s i t i v ee r r o r ) 即，非重复元素被错误地报告为重复元素， 和误否错误( f a l s e n e g a t i v ee 玎0 l r ) 即，重复元素被错误地报告为非重复元素。 为了解决上述闯题，我们前面已经介绍了精确副本检测方法( 缓存当前窗口 元素的方法) ，下面我们将给出另一个被前人用于数据流副本检测的近似方法。 计数型b l o o mf i l t e r 最近，文献【9 】提出使用计数型b l o o mf i l t e r ( c o u n t i n gb 1 0 0 mf i l t e r ( c b f ) ) 在滑 动窗口模型上进行副本检测。他们使用c b f 保存当前窗口中所有元素的信息。随 着数据流中的新元素的不断到达，我们也可以通过将对应计数器的值加1 来动态 更新c b f 中信息。因为c b f 中计数器的值表示映射到该计数器的元素的个数，所 以当一个已经插入c b f 的元素离开当前窗口时，c b f 只需要将该元素的对应的计 数器的值减l 。因此，只有当映射到某个计数器的所有元素都已经过期( 即离开 当前窗口) ，该计数器的值才能降到o 。这相当于从c b f 中删除这些过期的元素。 然而，只有知道该过期元素是那一个，才能在c b f 中进行过期元素的删除操 作。然而在许多数据流环境下，这个信息是很难获得的。例如：如果当前需要删 除c b f 中最老的元素，那么需要知道该最老元素所对应的计数器位置，但是这个 信息是不可能从c b f 中直接得到的而且维护这样的信息需要庞大的额外空间。另 外，对于数据流这样的多样数据集，某些元素的频率可能达到几千甚至几万。此 时，如果给每个计数器分配较小的空间，那么可能在新的数据元素插入时引发频 繁的计数器溢出；反之，如果给每个计数器分配较大的空间，那么将导致存储空 间的极大浪费并且也不一定能够避免计数器溢出情况的产生。 2 3 相关工作 最近，文献 9 首先研究了基于b l o o mf i l t e r ( b f ) 技术上数据流环境下的副本 检测问题。他们考虑了三种窗口模型：界标窗口、滑动窗口和跳跃窗口。对于界 标窗口，他们使用不加任何变化的b f 来探测副本，但是没有考虑到b f “满 的情况。对于滑动窗口，他们使用计数型b f ( 将b f 中的比特位改为计数器) 来提供过期元素的删除操作。然而计数型b f 存在着在此应用下的各种问题( 我 们已经在前面给出) 。对于跳跃窗口，他们把一个庞大的跳跃窗口切割成多个子 窗口，然后使用大小相同的b f 来表示各个子窗口。这样跳跃窗口可以通过添加 和去除子窗口的b f 来完成跳跃。 i 在许多数据流环境下，分配给b l o o m f i l t c r 的空间要远小于数据流大小。但是随着数据流数据元素源源不 断到达，b f 中的o 值比特位个数将不断减少，一直到所有比特位都被置为1 ( b f “满”的情况) ：同时 误是概率也相应的不断增大，一直到极限值l ，此时所有非副本元素都会被报告为副本。 1 3 第2 章滑动窗口上数据流副本检测的有效算法 随后，文献 1 0 】基于计数型b f 提出了界标窗口下新的副本检测的概要结 构一稳定性b f ( s t a b l eb l o o mf i l t e r ( s b f ) ) 。因为普通b f 不可能存储数据流的 所有历史元素，而且数据流中当前的元素总是比久远的元素重要。根据数据流 的这个重要特征，s b f 通过删除存储在s b f 中的较老元素来为新到达的元素腾 出空间。为了区分不同元素的新旧，s b f 使用计数器的值来表示映射到该计数 器的元素的新旧关系。该方法能够避免b f “满 的情况。 另一个在数据流环境下进行副本检测的方法就是高速缓存方法，该方法已 经被广泛用于数据库系统、操作系统以及最近w e b 爬虫爬行( w 曲c r a w l i n g ) 5 7 5 8 的网页u r l 缓存中。精确的数据副本删除在非数据流环境下已经被前 人广泛研究，而且这里有着许多有效的算法 6 0 。对于在非数据流环境下近似 的成员关系查询，b l o o mf i l t e r 技术经常被扩展用于不同的场合 5 2 6 1 。如， 文献 5 5 ，扩展b f 用于提供不同数据元素的频率查询。文献 6 2 使用b f 来计 算不同元素的个数。另外，这里存在副本检测的另一个分支一模糊的副本检测 ( 如z z yd u p l i c a t e sd e t e c t i o n ) ，该问题目的是区分存储在同一个数据源下表示相 同对象的不同表示且主要用于数据清除、数据挖掘和数据整合。 本章主要基于b l o o mf i l t e r 技术，提出了一个在数据流滑动窗口上进行副本 检测的概要数据结构d e c a y e db l o o mf i l t e r ( d b f ) 和一个动态更新d b f 的有 效算法。与前面计数型b l o o mf i l t e r 不同，d b f 不需要额外的空间就可以保证 滑动窗口的移动，而且也避免了计数器溢出的情况。而且，我们的方法只可能 存在误是错误而没有误否错误。为了减低动态更新d b f 的时间以及概要的存 储空间，我们引入了数据流分块和更新延迟技术。另外，通过分析，我们给出 了d b f 处理每个元素的平均时间复杂度以及查询结果的误差概率最小上界。 2 4 基于衰减型b l o o mf i l t e r 的滑动窗口上副本检测 这部分将给出我们方法的详细描述。 2 4 1 抽象性描述 通常情况下，滑动窗口上数据流的副本检测过程为：总是使用一个数据概要 存储当前窗口中数据元素的成员关系，对于一个新到来的数据元素，首先通过查 询这个概要来判断该元素是否是副本，然后更新当前数据概要。因此，整个过程 分为：查询操作和数据概要的更新操作。首先我们引入了数据流的分块技术，以 此来提高对数据流的处理速度和降低数据概要的存储空间。从表面上看，分块技 术与我们的问题相冲突( 我们的目的是检测滑动窗口上副本) ，因为副本检测需 1 4 第2 章滑动窗口上数据流副本检测的有效算法 要处理单个数据元素。实际上，分块技术主要是用于数据概要的更新，即通过数 据块对数据概要的稀疏更新来果代替单个元素的频繁更新。 我们将数据流划分成多个大小相等的不重叠的数据块。为了限定块的大小， 我们引入了一个门限值，( 7 1 是整数且胗 p d ) ，如图2 1 所示：对每个数据块 按照o ，1 ，2 ，进行编号并且编号越小表示该块所包含的数据元素越老。为了简 化表达式，我们假定窗口大小形和块的大小丁都为2 的指数，那么当数据流中 所见元素的个数超过时，那么当前滑动窗口至少时涵盖助7 个数据块最多时 涵盖助n 1 个数据块。无论任何时间点上，根据丁和的大小，以及当前所见 数据流中的元素的个数，我们分配给每个数据块以下5 种状态中的一种。 过期状态( 脚姚d ) ：数据块中的所有元素( 按照到达的时间顺序) 都比最 新的个元素老。 处于销毁状态( 叻沈，如s 驴“c f i o 门( 己，d ) ) ：数据块中存在部分元素比最新的 个元素老，且其余的元素却属于当前最新的的个元素。 活动状态似c f f v e ) ：数据块中所有元素属于当前最新的的个元素。 处于构造状态( 跏沈r 门j 驴甜c f f o 门( u o ) ：数据块中存在部分元素属于当前最 新的的个元素，且其余的元素还没有到达，即不可见。 非活动状态沏口c f f v p ) ：数据块中所有元素都还没有到达。 二二二 盈豳 r 矿 b _ w ，- |b | = u n d e rd e s t r h c t t o n u n d e rc o n s t r u c t i o n 图2 1 数据流中数据块的划分 注意：表示由我们概要数据结构表示的元素的实际个数且 w 。 每个数据块都要按照时间顺序经历非活动、处于构造、活动、处于销毁、过 期状态。我们对每个数据块的处理过程如下：对于每一个新到达的元素，如果当 前存在一个处于构造状态的数据块，那么将该元素插入该块中；否则，创建一个 处于构造状态的数据块并将新元素插入该快中。当处于构造状态的数据块的状态 中的元素个数达到丁时，我们将其状态改变为活动状态并且( 如果当前存在一个 处于销毁状态的数据块) 修改处于销毁状态的数据块的状态为过期。同时，当活 动状态中存在数据元素比最新的个元素老，我们标记该块为销毁状态。我们 j 憾 帆 眦 咖 娜胁 砌 第2 章滑动窗口上数据流副本检测的有效算法 将一个数据块的从处于构造状态到活动状态称之为块的构造时间段。注意，每个 块的构造时间段涵盖r 个元素。 尽管上述处理数据块的过程比较复杂，但是实际上我们只需要处理当前滑动 窗口中的数据块，即：处于构造的数据块、活动的数据块和处于销毁的数据块， 因为非活动的数据块和过期数据块对我们所要解决问题的结果不产生任何影响。 2 4 2 形式化描述 这里，我们的思想就是设置当前数据块不同剩余寿命值来区别当前滑动窗口 中数据块的状态，上述过程可以描述如下：我们将处于当前滑动窗口的数据块分 配以不同的剩余寿命值：当前最新的数据块，即处于构造的数据块，为助弭1 ， 除此之外，我们分配当前的最新数据块为彤仃，如此类推，如果存在处于销毁 的数据块，其剩余寿命值为l 。如果数据块处于过期状态，则其剩余寿命值为o 。 为了区分滑动窗口上不同数据块中的元素，我们使用该块的剩余寿命值来标识该 元素。例如：假如元素p l 和元素e 2 属于同一数据块，那么，妮( p 1 ) = ，咖( p 2 ) ，反之， z 咖( 9 1 ) z 谵( 9 2 ) ( 这里蜘( p ) 表示元素e 所在数据块的寿命) 。因为新的元素不 断到达导致新的数据块的不断到达，我们需要不断对当前滑动窗口中数据块的剩 余寿命值减1 来更新数据块的状态。当某个数据块的剩余寿命值从1 降为0 ，那 么意味着该块已经从处于销毁状态转化为过期状态。 上述剩余寿命值方法能够很好地描述数据块的状态变化过程，但是对于每一 个新到达的数据块我们需要更新当前窗口中所有数据块的剩余寿命值。因此，为 了避免频繁的更新，我们引入了延迟更新技术。其大意就是，对于新来的数据块 我们并不是立即对所有数据块的剩余寿命值减1 ，而是延迟到m ( 约c 孵， c 是常数，我们将在参数设定那一节给出其实际值) 个数据块的到来后才对所有 数据块的剩余寿命值减m 。这里，肋定义为延迟因子并表示所要延迟的数据块 个数。 数据流环境下，滑动窗口可以被看作为一个时间衰减函数【6 4 】【6 5 】：已知滑 动窗口的大小肌该函数可以被定义为胎) = 蜘盯垅g ，当元素p 处于当前窗口 时，他) o 否则兀p ) = 0 。为了有效实现上述过程，我们基于b l o o mf i l t e r 技术提出 了新的数据结构：衰减型b 1 0 0 m 矗l t e r 定义l ( 衰减型b l o o mf i i t e r ( d b f ) ) ：已知存储空间g ( = 职j ) 比特位和 滑动窗口大小，脚f 是由一组计数器脚印7 ，脚可抽7 组成。d b f 的动态 更新算法如a l g o r i t h ml 。其中每个计数器分配d ( = f i o g 妙r + 功+ 2 ) 1 ) 比特位并且其 最大值为阶加+ 2 最小值为o 。 具体来说，我们使用计数器来保存映射元素的剩余寿命值。首先，我们初始 1 6 第2 章滑动窗口上数据流副本检测的有效算法 2 5 误差概率分析 在这部分，我们对d b f 的性能和误差概率进行深入分析。为了讨论的简单 性，我们假设加= 0 ，因为我们会在后面指出尬的取值只影响到d b f 的更新效 率，对于误是概率没有影响。另外我们假设对于任何整数v ，vm o d0 = 0 不难发现，实际上d b f 所保存元素的个数往往不等于滑动窗口的大小。假 设表示d b f 实际所保存元素的个数。如果当前所见数据流的元