（计算机软件与理论专业论文）基于屏蔽汇总技术的数据流处理算法.pdf

中文摘要 与传统数据密集型应用相比，诸如网络监控系统等顺序产生的实时数据无法 精确存储在数据库中，这种数据序列被称为数据流。数据流的典型特点是，其存 储消耗具有潜在的无界性，其产生次序、间隔等统计特性具有不确定性，因此， 数据流处理的算法需要具备以下的特点：1 ) 算法复杂度必须是次线性的，输出 结果可以是近似的；2 ) 算法能够实时处理数据流输入线性复杂度算法不能处 理数据流的存储，查询和分析处理，因此，通过屏蔽或汇总数据流来控制次线性 复杂度存储消耗成为数据流研究的重要内容本篇论文通过对数据流上频繁项 ( 集) 发现、分布数据流并上聚合函数估算和肛中值点( k - m e d i a n ) 搜寻，研究 数据流处理的屏蔽和汇总的基本策略，主要贡献有： 1 基于在线屏蔽策略，提出数据流上拒真的频繁项( 集) 发现，使用 o ( s 一1 l n ( 2 5 1 ) ) 存储以至少1 6 概率输出频繁项；使用o ( 譬l n ( s - 1 d - 1 ) ) 存 储可靠挖掘边界频繁项集( 频繁项集的浓缩表示) ； 2 基于采样屏蔽策略，提出滤除分布数据流中的冗余和不一致的算法，应 用m i n - w i s e 哈希采样数据流而获取均匀样本集。由于获取的样本集不受分 布流中冗余和不一致数据影响，能够准确估计聚合函数值，并进一步应 用m i n - w i s e 哈希方法采样位置流( 1 0 c a t i o ns t r e a m s ) 来搜寻“中值点； 3 基于汇总数据流策略，提出数据流上缸中值点的快速估算算法，应用空间 分割的汇总结构控制存储复杂度。不同于位置流中的频繁更新，数据流 上k 一中值点需要单遍扫描庞大数目点集来获取近似中值点集。研究发现分 割粒度不是影响肛中值点近似程度的直接原因，避免精细分割产生指数增长 的存储消耗问题。 本文的研究成果可广泛应用于数据流相关的应用，如金融交易数据的处理、传感 器网络数据的分析、以及网络实时监控等领域。 关键词：数据流，数据流挖掘，数据流查询。 分类号：t p 3 1 1 a b s t r a c t r e c e n t l ye m e r g i n gd a t a - i n t e n s i v ea p p l i c a t i o n sn s u a n yg e n e r a t es oc a l l e dd a t a s t r e a m si nu n c o n t r o l l a b l ep r o p e r t i e s ，c o m i n go r d e ro ri n t e r v a lf o re x a m p l ew h i l ea l g o - r i t h m sm a yc o n s u m ea l m o s ti n f i n i t em e m o r yw i t hr e s p e c tt ol i m i t e ds p a c ea v a i l a b l e t h e r e f o r e ，a na l g o r i t h mf o rd a t as t r e a m si sc o n s t r a i n e dt ot h ef o l l o w i n gr e q u i r e - m e n t s ：1 ) i tm u s tr u ni ns u b l i n e a rs p a c ew h i l ei t so u t p u tm a yb ea p p r o x i m a t e ；2 ) i tc a np r o c e s si n p u t si na no n l i n ew a y e i t h e rs h i e l d i n gp a r t so fd a t as t r e a m so r s u m m a r i z i n g d a t as t r e a m sc a nb ea m o n ga l t e r n a t i v es t r a t e g i e sf o rd a t as t r e a m sp r o - c e s s i n gw h e ni tc a nc o n s u m en om o r et h a ns u b l i n e a rs p a c e i nt h i st h e s i s ，w es t u d y s e v e r a lp r o b l e m so fd a t as t r e a m s ，i n c l u d i n gm i n i n gf r e q u e n ti t e m ( s e t ) s ，e s t i m a t i n g a g g r e g a t i o nf u n c t i o n si nd i s t r i b u t e de n v i r o n m e n t sa n ds e a r c h i n gk - m e d i a nw i t ht h e f o l l o w i n gc o n t r i b u t i o n s ： 1 b a s e do no n l i n es h i e l d i n gp a r t so fd a t as t r e a m s ，w ep r o p o s ef a l s en e g a t i v ea l g o r i t h m sf o rm i n i n gf r e q u e n ti t e m ( s e t ) so rm a x i m a lf r e q u e n ti t e m s e t s u s i n g o ( s 。l n ( 2 5 。) ) m e m o r y , o u ra l g o r i t h mc a no u t p u tf r e q u e n ti t e m sw i t hp r o b - a b i l i t yo fa tl e a s t1 6w h i l ec a p t u r i n gm a x i m a lf r e q u e n ti t e m s e t sa tt h ec o s t o fd ( 譬l n ( s - 1 j - 1 ) ) 2 b a s e do ns a m p h n gd a t as t r e a m s w ep r o p o s ea l g o r i t h m sf o rf i l t e r i n go u t 静 d u n d a n ta n di n c o n s i s t e n td a t ah i d d e ni nd i s t r i b u t e dd a t as t r e a m s o u ra l g o - r i t h m sc a nl e a dt ou n i f o r ms a m p l e sa n da p p r o x i m a t es o l u t i o n st oe s t i m a t i n g s u c ha g g r e g a t ef u n c t i o n sa sa v e r a g ea g g r e g a t ef u n c t i o na n dk - m e d i a n 3 b a s e do ns u m m a r i z i n gd a t as t r e a m s ，w ep r o p o s eat i m e - e f f i c i e n tc o m p u t a t i o n o fk - m e d i a nu n d e rm e m o r yc o n s t r a i n t s i na d d i t i o nt od a t a - i a t e n s i v ea p p l i c a t i o n s ，o u rr e s e a r c h e sc a nb ea p p l i e dt oc o m p u - t a t i o n a lg e o m e t r y , m a s s i v eg r a p h ，m a c h i n el e a r n i n g ，p a t t e r nr e c o g n i t i o na n de t c k e yw o r d s ：d a t as t r e a m s ，d a t as t r e a m sm i n i n g ，q u e r y i n gd a t as t r e a m s 图目录 2 1 支持度8 ( s u p p o r t ) 的影响“= s l o ，6 = 0 1 ) 2 2 支持度阈值s ( s u p p o r t ) 的影响“= s 1 0 ，j = o 1 ) 2 3 误差e 的影响0 = 0 1 ，6 = 0 1 ) 2 4 可靠性参数6 的影响 2 5 流长度( l ) f t l 5 1 6 d 1 0 0 0 k ) 2 6 数据流次序的影响 2 7 全项集大小的影响( t 1 5 1 6 d 1 0 0 0 k ) 3 1 内存( m e m o r y ) 消耗 3 2 项集挖掘的内存开销( m e m o r y ) ， 3 3 项集挖掘的时间开销( t i m e ) 4 1 4 2 4 3 4 4 4 5 4 6 5 1 5 2 5 3 5 4 5 5 6 1 6 2 6 3 6 4 分布流的体系结构( 更新流u p d a t es t r e a m s 以，节点l 和请求d e m a n d ) 4 5 网络监测4 8 逻辑拓扑结构6 2 参数z i p f 秘在两个节点上的影响6 4 节点个数fv s 相对误差n ( e r r o rr a t e ) ，6 4 h - 取样v s c 一取样6 6 位置流产生的场景 标准配置环境中的距离和 冗余和不一致的位置流 哈希函数个数的影响 运动时间 ( 1 - e ) 占优的例子 1 一e _ 占优和密度间的关系 ( 1 一e ) 一占优的分割所引入附加误差的上界 数据集的不同静态特性对聚类的影响 船嬲卯勰凹凹； 如铊铊 鼹弘仍 s 8 8 ；8 g ； 6 5 6 6 6 7 6 8 6 9 图目录 极端数据集， 真实数据集( r e a ld a t as e t s ) 上的测试 进化数据流( e v o l v i n gd a t as e t s ) 密度阂值= 击对聚类的影响 初始分割宽度( c e l lw i d t h ) 对聚类的影响 9 3 9 5 9 5 9 6 9 6 表目录 1 1 数据库主要学术会议与数据流研究 1 2 在线算法和在线屏蔽算法的比较 5 7 2 1 算法内存复杂度1 5 2 2 i ，i 的c r 一值2 2 2 3 表2 2 的6 ，值，+ 2 2 2 4 改变支持度阈值s ( z i p f = 1 5 ) 2 4 2 5 改变z i p 渗数( s = 0 0 0 1 ) 2 4 2 6 关键区间测试( z i p f = 1 5 ，s = 0 1 ，e = s d o ) 2 5 2 7 支持度阈值s ( s u p p o r t ) 的影响( t i o 1 4 d 1 0 0 0 k ，e = s d o ，6 = o 1 ) 2 6 2 8 支持度阙值8 ( s u p p o r t ) 的影响( t 1 5 1 6 d i o o o k ，e = s z o ，d = 0 1 ) 2 6 2 9 误差e 的影响( t i o 1 4 d i o o o k ，8 = o 1 ，j = o 1 ) 2 7 2 1 0 误差e 的影响( t 1 5 1 6 d i o o o k ，s = 0 1 ，6 = 0 1 ) 2 8 2 i i 可靠性参数6 的影响( t i o 1 4 d i o o o k ) 2 8 2 1 2 流长度l 的影响( t 1 5 1 6 d 1 0 0 0 k ) 2 9 2 1 3 数据流次序的影响2 9 2 1 4 全项集大小的影响( t 1 5 1 6 d 1 0 0 0 k ) 3 0 3 1 d - 鲁棒4 0 3 ，2 真实数据上的完全率和准确率4 1 3 3 数据流长度的影响( 列m a , x m i n a v g 单位是) 4 1 3 4k 值估计4 3 3 5 t 1 0 1 4 d 1 0 0 0 k 上的正最优覆盖4 3 3 6t 1 5 1 6 d 1 0 0 0 k 上的矗最优覆盖4 3 3 7 乒最优覆盖的势4 3 4 1 两个局部样本集的合并，5 6 4 2 拓扑和数据参数6 3 v m 表目录 4 3 变化参数t 和垂( 1 0 k 个哈希函数) 4 4 真实新闻的更新流( 1 k 个哈希函数) 5 1 缺省参数值 6 1 算法的缺省参数 6 2 数据产生器参数 9 1 9 1 弘 第一章 引言 与传统数据密集型应用相比，诸如网络监控系统等顺序产生的实时数据无法 精确存储在数据库中，这种数据序列被称为数据流。数据流的典型特点是，其存 储消耗具有潜在的无界性，其产生次序、间隔等统计特性具有不确定性。数据 流典型应用场景是大规模网络管理，它需要查询路由器所路由的i p 包统计信息来 实时监控网络运行状态。例如，查询某段时间内流量超过阈值的i p 地址对。完 成上述查询需要存储路由的每对i p 源一目地址对的流量，由于路由器路由的i p 包 和i p 源一目地址对的个数都可能非常庞大，精确地记录每对i p 地址的统计信息超 出现实存储空间。传统数据库管理系统不能持久存储、精确计算和反复访问数据 流，因此，通过屏蔽或汇总数据流来达到次线性复杂度的存储消耗成为数据流 处理的现实考虑。在理论上，数据流研究丰富大规模数据和有限计算资源，特别 是有限存储资源这一基本矛盾的研究；数据流研究和以多项式复杂度为目标的算 法研究有本质的不同；数据流研究强调传统数据库管理中的线性复杂度算法不能 够处理数据流的存储、查询和分析处理。 1 1 数据流特点 从2 0 世纪6 0 年代末开始，独立于具体应用的数据被d b m s 统一管理起来，实 现数据资源的整体管理。在这个系统中，数据被精确和持久地存储在相对慢的存 储设备上以用于并发访问。完成持久存储、精确计算和反复访问所需要的高性能 系统、数据完整性、系统可维护性和可靠性得到充分研究。随着i n t e r n e t 的日益 延伸和自动数字设备的广泛使用，其产生的数据超出现有信息系统能够进行持久 存储、精确处理和反复访问的限度，如电子银行和信用卡业务中记录的事务数 据、卫星传输回来的高清晰地理图像数据、天文望远镜观察到的光学数据、气象 卫星测量到的气象科学数据、传感器网络中产生的感应数据和数据库管理系统 1 j 引言 中记录的事务日志等。相对于传统数据库中的静态数据1 ，本文认为数据流有以 下的基本特点： 1 存储消耗的潜在无界性i i ：相对于有限存储空间，数据流应用中产生的数据 不仅长度，而且数据值域几乎是无界的，如网络监控中存储每对i p 源一目地 址对流量可能需要消耗2 3 2 2 3 2 存储单元，同时需要处理无数的i p 包； 2 不确定性：数据产生的次序、间隔等统计特性事先不能预测，在极端情况 下，数据产生的速度能超出系统可以读入的限度。 m a y u rd a t a r 和r a j e e vm o t w a n i 等【1 】从数据库角度总结数据流的四个基本特 1 数据以在线方式输入到系统中； 2 数据输入的次序是系统不可以控制的； 3 从理论上说，数据流的长度是无限的，在实际中远远超过系统能够持久存 储、精确计算和反复访问的能力； 4 除非显式地存储数据，对“流过”的数据不可以再次访问，或访问的代价是 高昂的。 一方面，上述界定既包含数据流本身的特点，也包含了对数据流处理的算法要 求，如单遍扫描数据集的特点应该被认为是数据流处理的策略或方法，而不是数 据流本身的固有属性；另一方面，上述界定仅仅认为，因为数据流长度在理论上 是无限长，所以不能精确存储数据流。其实，不能存储数据流不仅是因为其长 度，而且是因为其值域在理论上也是无穷的。如果某个路由器仅仅路由1 0 ，0 0 0 不 同i p 地址对，那么尽管i p 包个数庞大，对查询流量大于某个闽值的i p 地址对也不 构成挑战。但是当i p 地址对空间远远超出现实存储时，数目不大的i p 包也使许多 查询变得困难；最后，因为无界的数据流不可能处于存储状态，其产生或处理只 能瞬间即逝，上述界定中所强调的，庞大数量的数据流是依次产生并被输入到系 统或算法中去，这对揭示数据流本质没有太多帮助因此，本文总结的数据流两 个基本特点仅仅扣住潜在无界性的数据流输入和有限存储的主要矛盾，而数据流 的不确定性是数据流研究的压束性条件。 g c o t m o d e 和s m u t h u k r i s h n a n 2 从算法角度理解数据流，认为算法为了计 算数据流需要维护一个巨大的表i i i 。如进行流量查询，这个表中的每个单元存 储某对i p 地址的流量。每处理一个i p 包，将对应的i p 地址对的流量增加该包的容 量。通过这个巨大的表可以对数据流进行精确查询和处理。由于i p 地址对的空 2 1 引言 间大小是2 3 2 2 3 2 ，需要2 3 2 2 3 2 个存储单元来存储这个巨大的表v 。在此基础上， 根据对表存储单元更新方式不同，他们抽象出三类基本的数据流模型： 1 时间序列模型( t i m es e r i e sm o d e l ) ：算法以某种次序访问表的每个存储单 元，访问过的每一单元值不会发生改变； 2 寄存器模型( c a s hr e g i s t r ym o d e l ) ：单元值只可以单调增加。对于利用单 调性的算法而言，这是个重要条件； 3 转门模型( t u r n s t i l em o d e l ) ：单元值不仅可以增加，也可以减少，甚至可 以删除存储单元，这是最一般的数据流模型。 上述的数据流模型从算法角度深刻地刻画了数据流在不同应用场景下的本质特 征，反映数据流处理的特点和难点：潜在无界性的数据流和有限存储空间但 上述模型不是数据流本身的固有属性，而是数据流所具有的属性对算法所产生的 影响。 1 2 数据流处理算法的基本要求 因为数据流本身固有属性，完成持久存储、精确计算和反复访问的高性能传 统数据库管理系统不能够处理大规模瞬时数据流的输入，众多研究机构和大学提 出了各自的实验性数据流管理系统d s m s ( d a t as t r e a mm a n a g e m e n ts y s t e m ) ， 如 3 1 n 等。在传统数据库管理系统的高性能、数据完整性和系统可维护性及可 靠性的基础上研究了数据流的查询语义【5 】【6 】和查询优化 7 s 1 1 9 】。这些系统基本 都有一个能够快速吸收数据流的底层结构和能够进行复杂运算的上层结构，系统 采取两个基本策略，或是屏蔽大规模数据流输入，或是通过汇总数据流输入，不 管采用何种处理策略，我们总结数据流处理算法应该满足以下的基本要求： 1 其复杂度v i 相对于数据流的长度和值域必须是次线性的，输出结果可以是近 似的； 2 算法能够实时处理数据流输入。 因为数据流的潜在无界性属性，必然要求其处理算法只能够使用次线性的空间代 价来计算( 或近似计算) 数据流；因为计算资源的有限性，在许多情况下算法 只能产生近似的结果，而且在许多现实应用中，近似结果是可以接受的；实时产 生的数据流必然要求处理它的算法能够对输入的数据做出及时的反应，即使算法 能够屏蔽输入的数据，但作出实时反应也是在线分析等应用的本身要求。在上 3 i 引言 述的基本要求中，对算法次线性复杂度的要求是最为基本的要求，也是对算法设 计最有影响的限制条件。 m u t h u k r i s h n a n 2 总结数据流处理的基本数学方法和算法技术，并提出了数据 流研究的可能方向，他的综述可以看成是数据流处理算法的g o o g l e i j l 擎，提供了 丰富的链接指针。本篇论文重点围绕数据流的潜在无界性和计算资源有限性这一 突出矛盾，强调数据流处理算法要满足次线性复杂度这一基本要求，总结数据流 处理算法的两个基本策略：屏蔽或汇总大规模数据流输入。 屏蔽数据流的基本技术可以是采样( s a m p l i n g ) 或在线处理( o n f i n e ) 【1 0 】， 目的是有选择地丢弃输入的数据流，仅消耗次线性的存储就能从部分数据流上得 到近似解。对于采样屏蔽，由于数据流的基本属性导致取得所要求的样本集是困 难的；在线屏蔽的基本思想直接来源于在线算法( o n u n ea l g o r i t h m s ) 的研究：在 线算法所要求的及时“决策”在数据流处理上可以理解为当算法耗尽存储时，如 何及时决策，通过丢弃部分数据来腾出存储空间，被丢弃的数据实际上相当于被 算法屏蔽的数据。在线屏蔽和在线算法的一个基本不同点是，在线屏蔽不能访问 已经访问过的数据，当然也不能访问未访问过的数据；在线算法可以反复访问以 前的数据，但不能访问以后的数据。从这个意义上来说，在线屏蔽是更为严格的 在线算法。在线屏蔽和采样屏蔽的共同特点都要丢弃( 屏蔽) 部分数据，同时能 够得到近似解，不同点是采用了不同的屏蔽策略。 汇总大规模数据流的输入可以减少存储消耗，原因在于汇总信息的存储消耗 远远小于细节信息( 或数据流本身) ，通过遗失数据细节来换取数据存储空间的 缩减在数据流研究中占有重要部分。汇总方法依靠”概要“( s y n o p s i s ) 的汇总 结构来表示和存储数据流的聚合属性，算法可以从汇总结构( s u m m a r y ) 产生近 似解。汇总数据流方法所要解决的主要矛盾是，汇总信息粒度和计算近似度的折 中：汇总信息消耗少的存储，但遗失细节信息，导致计算结果偏离精确解；细 节信息需要消耗多的存储，能够导致精确的解。m u t h u k r i s h n a n 2 所提到的树方 法( t r e em e t h o d ) 作为基本的算法技术反映了汇总粒度和存储消耗的折中。当中 “层”( 1 e v e l ) 的概念反映了不同粒度层次上的汇总结构。 b b a b c o c k 、s b a b u 、m d a t a r 和r m o t w a n i 等f 1 1 强调处理数据流的算法只 能单遍扫描数据流，并且将这一要求作为数据流处理算法的基本特征。我们的理 解是，单遍扫描数据流是算法设计的一个可行的策略，而不是数据流处理算法本 身固有的属性。面对在理论上无界的数据流以不可控的次序输入到算法中，而该 算法只有有限的存储空间，算法必须忘记一些信息来节约存储，那些被忘记的信 息对算法来说是没有办法恢复的。因此，在以后论述中不再强调算法单遍扫描数 据流，论文中的数据流处理算法都是单遍扫描数据流的。 4 1 引言 l 主要学术会议研究性论文数据流论文比例( )分会( s e s s i o n )数据流分会比例( ) s i g m o d 2 0 0 24 249 1 4 1 7 v l d b 2 0 0 2 6 9 81 12 129 i c d e 2 0 0 25 4351 800 s i g m o d 2 0 0 3 5 3 81 52 341 7 v l d b 2 0 0 37 51 41 82 541 6 i c d e 2 0 0 35 1471 700 s i g m o d 2 0 0 46 981 12 229 v l d b 2 0 0 48 11 72 02 441 6 i c d e 2 0 0 4 6 36 92 129 s i g m o d 2 0 0 56 51 52 32 252 3 v l d b 2 0 0 58 41 2 1 42 827 i c d e 2 0 0 56 7692 628 i 总计7 7 41 0 5 1 42 6 13 41 3 表1 1 ：数据库主要学术会议与数据流研究 1 3 数据流研究进展 开始于八十年代的数据流研究成为当前多个学科的研究热点。早在1 9 8 0 年， m u n r o 和p a t e r s o n 1 1 提出使用d ( ；) 空间复杂度通过p 次遍历来获得分位数的 方法。不久，b o y e r 和m o o r e 1 2 也提出了单遍扫描数据集来搜取多集中频数 超过一半的元素方法。再后来， 1 1 1 和 1 3 】进一步研究了算法复杂度和扫描数据 集次数间的关系。这些早期的研究从理论上开启了数据流研究。二十世纪九 十年代末期以后，由于数据流在数据密集型应用中广泛出现，数据流研究真正 成为当前研究热点。数据流研究的论文数量在数据库研究领域最主要国际学术 会议s i g m o d 、v l d b 、i c d e 呈上升趋势，近年来录用的数据流论文情况列在 表1 1 中，在总共录用的7 7 4 篇文章中，数据流论文占1 4 ，在总共2 6 1 个主题分会 ( s e s s i o n ) 中，数据流主题分会占了1 3 。 在理论研究的同时，研究人员还构建了许多研究性的数据流管理系统，如n i _ a g a r a 1 4 1 、t r i b e c a 1 5 1 、h a n c o c k 1 6 、a u r o r a l l 7 、s t r e a m 1 8 1 、t a n g r a m 1 9 】、 t a p e s t r y 2 0 】和t e l e g r a p h 2 1 】等。这方面的研究工作包括设计新型的系统架构、 查询语言、资源分配、查询优化等。 除了数据库领域外，数据流研究还吸引了众多相关领域研究人员的兴趣，如 计算机理论和算法界f 2 1 2 2 】、计算几何【2 3 】【2 4 】、大规模图处理【2 5 】【2 6 和机器学习 以及模式识别【2 7 1 【2 8 1 等，这些相关领域都可能面对大规模数据输入，以及重复扫 描数据集的代价是难以忍受的应用需求研究的问题从早期的数据流上简单统计 量计算1 2 2 】【2 9 3 0 1 、频繁模式挖掘 3 1 】【3 2 至u 复杂的聚类模式的产生 3 3 1 1 3 4 1 和分类 5 i 引言 模式的抽取【2 7 】【3 5 】等。有影响的综述【1 】【2 】等从不同角度收集整理了数据流的研究 历史、进展和主要结果，本章集中阐述两个方面的内容：i ) 包含这些综述以后 的一些结果：i i ) 围绕数据流潜在无界性和存储有限性的矛盾所产生的算法设计思 想和主要成果。 1 3 1 数据流模型研究进展 随着对数据流本质理解的深化和应用范围的不断扩大，在三个基本数据流模 型( 时间序列、寄存器和转门模型) 的基础上，面向特殊应用的数据流模型不断 被抽象出来，除了【2 】所简要列出的模型外，我们又整理了散见于其他文献的典型 模型： 1 排列模型( p e r m u t a t i o ns t r e a m ) ：是寄存器模型的特例，存储单元值都不 相同( 所有存储单元可以构成一个集合) ，估计不同排列的编辑距离( e d i t d i s t a n c e ) 、估计排列逆序( i n v e r s i o n ) 对个数等得到研究； 2 滑动窗口模型( s l i d i n gw i n d o w ) ：关心数据流上最近的输入或某个时段上 的数据流【3 6 】 3 7 】； 3 分布流模型( d i s t r i b u t e dd a t as t r e a m s ) ：关于在物理上分布的多条数据流 的模型 3 8 3 9 1 ； 4 同步流模型( s y n c h r o n i z e ds t r e a m ) ：是一个特殊的分布流模型，同步更新 分布流相应的存储单元中的记录值： 5 位置流模型( 1 0 c a t i o ns t r e a m ) ：m h o f f m a n 、s m u t h u k r i s h n a n 和r a j e e v 鼬a n 【4 0 】从g p s 广泛使用中抽象出位置流模型，并进一步细分为初始 ( r e s e t ) 类型和增量( i n c r e m e n t a l ) 类型。 上述从具体应用中抽象出的模型揭示了新的应用需求，拓展了数据流研究和应用 范围，丰富人们对数据流本质的理解。有一点可以肯定，随着数据流研究的深入 和扩展，新的数据流模型会不断被抽象出来，这些新的模型反过来又催生新的研 究、应用。 1 3 2 数据流处理算法研究进展 围绕数据流潜在无界特点和存储空间有限现实，本章将数据流处理算法整理 为两大类别：或是基于屏蔽的算法，或是基于汇总的算法。基于屏蔽的主要思路 6 1 引言 表1 2 ：在线算法和在线屏蔽算法的比较 i 算法特点 在线屏蔽算法 在线算法 重复扫描数据不可以可以 控制输入次序 不可以不可以 精确存储数据不可以可以 实时反应不要求要求 输出结果可以是近似解可以是近似解 是有选择地丢弃数据流的输入，由于不同选择策略，产生不同的算法，解决不同 的问题，有两个基本技术可以采用，一个是在线方法，另一个是采样方法；基于 汇总的主要思路是对输入的数据流进行汇总，遗失数据细节来缩减存储消耗，有 两个比较典型的基本技术，一个是随机投影( r a n d o mp r o j e c t i o n ) ，另一个是嵌 入方法( e m b e d d i n gm e t h o d ) ，在这两个基本方法的基础上，近来也出现将多个 汇总方法组合使用而产生的组合汇总方法。 基于屏蔽的方法 在线屏蔽在线算法的主要特点是算法能够及时做出“决定”来快速响应外部的 输入【1 0 】在线算法可以重新扫描已经扫描过的输入，在当前做出决定的时刻是 不能扫描还没有扫描的输入。同时，数据输入次序是不能事先限定的。在线屏蔽 的基本特点是，当算法耗尽存储时，如何及时决定以丢弃部分存储数据来腾出存 储空间，腾出操作的结果就是有选择地丢弃( 屏蔽) 部分存储数据。同时，在线 屏蔽算法不能重复扫描已经扫描过的输入，或重复扫描的代价很大，但是不一定 要求实时做出对外部的响应，除非到要求输出时才输出计算结果。在线算法和在 线屏蔽算法都不能扫描还没有输入的数据，而且算法本身不能控制外部输入的次 序。所以在线屏蔽算法是结合数据流和在线算法特点的算法，它们详细的异同参 看表1 2 。 在线屏蔽算法一般都要在数据流处理中始终维护不变关系( i n v a r i a n t s ) ，根 据这些不变关系，算法有一些基本的处理技术；i ) 在内存消耗到一定限度后， 算法可以合并或丢弃数据来缩减存储，在这一过程中，算法必须维护这些不变 关系；i i ) 当算法发现所维护的不变关系遭到破坏时，算法重新建立这些不变关 系，在重建中，内存一般得到缩减。无论采用那种具体的技术方法，最终都是由 这些不变关系导出近似解。在线屏蔽算法往往在一定的间隔( 分段) 末来检查所 要维护的关系是否得到维护或内存使用是否溢出。因此，在线屏蔽算法跟分而 治之( d i v i d ea n dc o n q u e r ) 的算法有相似的地方，或者说在线屏蔽算法应用了分 而治之的思想。由分而治之的方法所启发产生的算法需要维护某个或某些不变条 7 1 引言 件，以及从不变条件导致近似解。 在线屏蔽算法在数据流处理中占有重要的地位，g s m a n k u 和r m o t w a n i 4 1 1 提出的l o s s y - c o u n t i n g 方法( 简写为l c ) 是典型的在线屏蔽算法。l c 将数据流 分为段，在每段的末尾删除小于阂值的计数器( 腾出存储) ，l c 的关键在于闽 值的确定( 如何选择丢弃的标准) ，并由此确定的阈值( 所维护的不变条件) 能 够导致次线性的内存消耗和近似解。其他的在线屏蔽算法 2 9 4 2 4 3 】有相同的思 路，并由此产生了一批数据流上有效的在线屏蔽算法。 采样屏蔽采样是屏蔽大规模数据输入的有效方法。z i vb a r - y o s s e f ，r a v ik u - m a r 和d s i v a k u m a r 4 4 研究了采样、汇总和在线屏蔽间的关系。基于随机决策 树模型，他们认为，三个方法中任何一个方法都可以衍生出另外两个方法，即三 种方法之间在许多应用实例中是等价的。有一点需要强调的是，在开始数据流研 究之前，在线算法、取样和汇总，如有关数据减少( d a t ar e d u c t i o n ) 的研究，都 已经广泛应用于数据库管理系统和大规模数据( m a s s i v ed a t a b a s e ) 处理。本篇论 文着重阐述取样方法来屏蔽大规模数据流时所遇到的特殊问题和解决方法。数据 流的潜在无界性、不确定性是导致获取所要样本集困难的根本原因。 往往以实时方式产生的数据流要求取样算法能够时间有效( t i m e - e f f i c i e n t ) 地 屏蔽数据流的输入并能获取所要的样本集：数据流的潜在无界性使得以固定概率 取样的样本数难以控制：不确定性的数据流产生样本偏斜。其中，对于有删除操 作的动态数据流，使得样本数可能远远小于所要求的。针对这些问题，研究人员 展开了系统的研究，从文献出现的时间顺序上可以看出这方面的研究在最近几年 越来越引起重视。 数据流上采样方法首推v i t t e r 4 5 1 的方法，该方法能够在事先不知道数据流长 度的条件下采得固定数目的均匀样本集，这一方法是许多采样屏蔽算法的基本采 样方法1 4 6 1 。但是对于带有删除的动态流，该方法还需要新的研究1 4 7 1 1 4 8 】，其原 因是删除操作的不确定性：算法无法预知删除，如果事前采样太多，会增加内存 消耗，如果事前采样太少，由于删除操作，使得样本数和其他统计特性不能得到 满足。 p h i l l i pb g i b b o n s 和s r i k a n t at i r t h a p u r a 3 9 研究了分布环境下采样的问题。 在分布环境中，单个节点上满足要求的样本集不一定能导致全局上的满足要 求的样本集，除非单个节点上的样本集间满足某种关系。他们建议的协调采样 ( c o o r d i n a t e ds a m p l i n g ) 方法能够在分布样本集上建立协调关系来获得所要求的 全局样本集。g r a h a mc o r m o d e 和s m u t h u k r i s h n a n 2 6 t i 开究了在多集中取得均匀 样本集的问题。在大规模的多集中，重复元素能够偏斜样本集，因为重复元素能 够以较高的概率被采样。相关的工作还有f 1 a j o l e t 和g n m a r t i n 4 9 】的消除重复 元素影响来估计不同元素个数的方法。对于采样屏蔽的批评声音可以在【3 1 】【5 0 】等 8 1 引言 文献的字里行间中找到，如宣称采样方法不能够处理转门模型的数据流，其实这 些问题在近来的文献【4 7 】【4 8 】中得到重视和逐步解决 基于汇总的方法 最新和最全面的有关汇总算法的综述是s u d i p t og u h a 和k y u s e o ks h i m 在v l d b 2 0 0 5 上的报告f 5 1 1 ，较早的文献是m u t h u k r i s h n a n 的综述【2 1 。因为潜在 无界的数据流和有限的计算资源，特别是有限的存储空间，数据流处理的一个重 要特征是再次扫描已经扫描过的数据流在许多应用是不可能的，或其代价是昂贵 的。解决这个矛盾的一个可以方向是，对数据流进行汇总，而丢弃细节信息。相 对于细节信息，汇总信息的存储消耗可以大大减少，能达到次线性的存储消耗。 这一方法所要解决的主要问题是，如何从汇总信息结构中获取( 估计) 不同粒度 上的细节信息：较细( 细粒度) 的汇总结构需要较多的内存消耗，但能够得到更 为准确的估计；反之，较粗( 粗粒度) 的汇总结构消耗较少的存储，但不能得到 准确的估计。关于存储消耗和近似度的折中方法的论文在数据流研究领域占有很 多的篇幅，很难将其详细总结，我们在其中选三个比较典型的视角来阐述其基本 思想：i ) 嵌入方法，将高维空间i i 嵌入到次线性低维空间中；i i ) 随机投影，将 高维空间随机投影到次线性的低维空间中；i i i ) 组合方法，组合多个缩减数据的 方法来建立汇总结构。 嵌入方法p i n d y k 5 2 提出的基： ：p - s t a b l e 方法将露嵌入( e m b e d d i n g ) 到f u 【啷卅中， 并且仅产生f 1 + i n e o ) ) 扭曲( d i s t o r t i o n ) ，这一结果立刻统一以前在l 1 和妒上 的一些结果【5 3 】 5 4 】，随后这个方法被拓展到p = 0 ，1 ，2 5 5 】【5 6 】。 随机投影方法随机投影的思想在数据流计数问题上得到充分体现。在c o u n t m i n 随机汇总结构( s k e t c h ) f 5 0 的基础上产生了一批的研究结果。g r a h a mc o r m o d e 和s m u t h u k r i s h n a n 3 1 1 将g r o u p - t e s t 的方法嵌入到c o u n t r a i n 的随机汇总结构 ( s k e t c h ) 中加快频繁项的输出速度。a n n ac g i l b e r t 和s u d i p t og u h a 等 5 7 】在 c o u n t m i n 中嵌入了g r o u p - t e s t 和二值区间( d y a d i ci n t e r v a l ) 而能估计不同 粒度上的近似计数问题，从而能快速维护数据流上的直方图( h i s t o g r a m ) 。因 此，c o u n t - r a i n 、g r o u p - t e s t 和d y a d i ci n t e r v a l 是随机投影方法的三个主要构件，并 将随机投影方法发展到一个比较完善的程度，展示了从汇总信息结构中抽取细节 信息的技术思想。其他文献应用这三个( 或部分) 构件解决了不同忍题，如p i o t r i n d y k 2 3 利用x c o u n t 汇总结构计算动态数据流上中值点估计问题，a n n ac g i l b e r t 、y a n n i sk o t i d i s 和s m u t h u k r i s h n a n 等 5 s l 应用类似于d y a d i ci n t e r v a l 的 区间来求解数据流上的近似分位数。 组合方法汇总数据中可能包含重复值的影响。滤除汇总中重复值的问题 在【2 6 】【5 9 】中得到研究，采用在汇总结构( s y n o p s i s ) 中再嵌套另外个随机汇 9 1 引言 总结构( 8 k e t c h ) 来滤除重复值。在 5 9 1 5 b ，f m 4 9 被嵌套在汇总结构中来滤除重 复