（计算机软件与理论专业论文）基于反馈机制的流数据查询.pdf

兰州大学硕士学位论文基于反馈机制的流数据查询 摘要 流数据查询是流数据处理中一个非常重要的研究领域，由于流数据到来的快速性和 大量性等特点，必须及时地对流数据进行处理，流数据的输入速率突然剧增会使查询系 统发生过载，将严重影响查询系统的响应速度和查询质量，查询系统有效的过载控制已 成为一个研究的热点；同时查询处理产生的结果数据流往往有很重要的参考价值，这样 就产生了流数据查询中对已产生的结果流再利用的问题。如何充分利用己得到查询结果 流也成为当前研究的一个重要课题。 目前查询系统的过载控制仍未达到理想效果，对查询结果流的利用也很少。因此本 文构建了基于反馈机制的流数据查询模型，并对该模型中的过载控制、查询处理和反馈 生成等问题进行了深入的研究，主要工作和创新成果体现在以下几个方面。 首先，构造了基于反馈机制的流数据查询模型，通过对连续查询的结果流进行反馈 树分类从而发现输出结果流的主要特征，并以此来对输入数据流进行评估，指导流数据 处理系统中过载控制的丢弃元组操作，最大可能的提高输出结果的准确度，在查询时以 反馈参数为指导还可以加快查询速度。 其次，在对a u r o r a 系统过载卸载的分析基础上，提出了改进的完备负载卸载路径 映射的重构方法和自适应的负载卸载路径映射的重构方法，从理论上的有效性进行了分 析，并对其算法进行了设计。 再次，设计了基于时间粒度的多层次滑动窗口的划分和动态维护方案和部分算法， 使的流数据查询可以在多个不同的层次进行，能进一步提高查询的准确度。 最后，采用了反馈树的方法生成反馈度参数，并对带有反馈度参数的反馈树的生长 和剪枝算法进行了设计。 关键词：流数据负载卸载时间粒度反馈树 兰州大学硕士学位论文 基于反馈机翻的流数据查询 a b s t r a c t s t r e a md a t aq u e r yi sav e r yi m p o r u m tf i e l do fd a t as t r e a mp r o c e s s i n g s t r e a md a t am u s t b el , r o e e s s e dp r o m p t l yt ok e e pl 巾w i t ht h e 蠡s td a t a 型, - r i v i n gr a t e t h ed a t as t r e a mi n p u tr a t e s h a 印i n c r e a s e 锄n a l t k et h eq u e r ys y s t e mt ob eo v e r l o a d , w h i c ha f f e c t st h eq u e r yr e s p o n s e s p e e d , t l a eq u e r yq u a l i t ys e f i o u s l y t h el o a ds h e d d i n go ft h e 矧既i md a t aq u e r ys y s t e m b o c o m e sar e s e a r c hh o ts p o t t h er e s u l ts n 宅a md a t ap r o d u c e db yq u e r yp r o c e s s i n go t x t e nh a s v e r yi m p o r t a n tr e f e r e n c ev a l u e s on 巩i t h er e s u l ts t r e a md a t ai nd a t as t r e a mq u e r yi s i m p o r t a n t h o wt of u l l ym a k e l 】s eo f t h eq u e r yr e s u l td a t as t l - e a ma l s ob e , c o l n c sa ni m p o r t a n t r e s e a r c hp r o b l e m n o wq u e r ym o d e lo f & a ms t r c s mc a n td e a lw i t ht h eo v e r l o a do f s y s t e me t t i e i e a t l y , a n d c a n tm a k e 懿lu o fr e s u l ts t r e a md a t ae i t h e r i nv i e wo ft h i s ，w ep r e s e n tad a d as t r e a m q u e r ys y s t e mb a s e do nf e e d b a c km e c h a n i s mm o d e l w eh a v em a d ead e e p l ys t u d yo ft h e m o d e la n dl o a ds h e d d i n go fd a t 8s t r e a mq u e r ys y s t e m o u rw o r ki sm a i n l yr e f i n e di nt h e f o l l o w i n ga s p e c t s ： f i r s t l y , w ec o l l s t r u c t1 3 d a t as t r e a mq u e r ys y s t e mm o d e lb a s e d0 1 3 f e e d b a c km e c h a n i s m w ec a ne v a l u a t et h ed a t as i l e o , n li n p u t , a n ds h 司, l t n go v e r l o a dm o l ee f f i c i e n t l yt h r o u g ht l a e c h a r a e t e r i s t i ep a r a m e t e r s 锄ef r o mc l a s s i f y i n gt h er e s u l td a t as t r e a mf e e d b a c kt r e e w i t ht h e p a r a m e t e rp r o d t l e e db yf e e d b a c kl a c e t h eq u e r yo v e l t h ed a t as t r e a mc a l la l s ob ep c r f o r m e d m o r ca c c u r a t e l y s e c o n d l y , ac o m p l e t e l yl o a ds h e d d i n gr o u t e rm a p ( l s r m ) e o m m l e t i o nm e t h o da n d 孤 a d a p t i v el s r mc o n s m t e t i o nm e t h o d 躺p r e s e n t e da 矗e ra n a l y z e dt h ea u r o r a sl s r m c o n s l l u c t i o 也 t h i r d l y , as l i a i n gw i n d o wm a i n t a i n i n gs c h e m ew i t hm u l t i - t i m eg r a n u l a r i t yi sd e s i g n e d , a n dw i t ht h a tw ec 1 1 1 1q u e r ys t e a md a t a1 1 1 0 1 屯a c c u r a t e l y l a s t l y , f e e , d b a e kt r e ei su s e dt op r o d u c et h ep a r a m e t e ro ft h em o d d ，t h eg r o w i n ga n d p r u n ep r o c e s s e so f t h ef e e d b a c k 岫a r ed e s i g n e d k e y w o r i o $ ：s l h t l n ld a t a ，l o a ds h e d d i n g - t i m eg r a n u l a r i t y ，f 剐b 4 c b t r ” n 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研 究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明出处。除文中已经注明引用的内容外，不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究成果做出重 要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：避! 日 期：兰盟堡竺自塑目 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰 州大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学 校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被 查阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用任何复制手段保存和汇编本学位论文。本 人离校后发表、使用学位论文或与该论文直接相关的学术论文或成果时， 第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：壅垒：l导师签名：胁日 兰州大学硕士学位论文 基于反馈机制的流数据查询 第一章绪论 近年来一种新的数据集的应用逐渐引起人们的重视，在这种应用中数据采用的不是静态数据关 系而是以快速的瞬时的流形式出现。本文将围绕这种流数据的查询处理进行展开，对其相关主题进 行研究和探讨本章主要讨论全文的研究背景、本文的主要研究内容以及本文的组织 1 1 研究背景 随着网络、电信和传感器技术的发展，在金融报价，网络监控、安全、电信数据管理、w e b 交 易日志分析、制造业、传感器网络等应用领域中出现了一种新的数据应用形式在这些应用中数据 以大量高速率的流形式出现，称之为数据流。由于传统的数据库处理技术不能很好的适应这种形式， 数据流上持续长时问的连续查询、聚类分析等实时处理的需求越来越迫切。 数据流是大量高速率连续到达的、潜在无限的数据有序序列【l l ，这类数据或其摘要信息只能按 顺序存叹并被读取一次或有限次，具有随时间动态变化的趋势，同时数据本身往往又是高维的，数 据流到达的速率不易被处理系统所控制，随时间变化不可预测，由于流数据长时问连续不断的到来， 所以存储整个数据流很不现实怎样利用有限存储空间对数据流中的数据进行快速有效的处理以获 取有用信息，为数据库及其应用研究带来了新的机遇和挑战，具有非常重要的意义 在流数据查询方面有两个有影响的研究小组：一个是s t a n f o r d 大学的r m o t w a n i 教授领导的研 究小组，研究侧重在数据流管理、数据流的连续查询和数据流的聚类方面。提出了不同于传统d b m s 的d s m s 2 1 ( d a t as t r e a mm a n a g e m e ms y s t e m ) 概念，另一个是u i u c 的c a g g a r w a l 和j h m 教授 领导的研究小组。他们的研究侧重在数据流分析方面，在聚类，分类、频繁项集挖掘和可视化等方 面做了大量研究工作，提出了倾斜时间窗口( t i l t o d 4 i m ew i n d o w ) 策略【3 川 国内对数据流处理的研究也正在发展中，有些学校和研究所正在对数据流进行研究。其中以东 北大学最为突出，宋宝燕、张立杰、陆岩、于戈提出了一种基于输出速率的代价模型( o u tr a t em o d e l ) 的适应性查询处理机制搠，欧征宇、宋宝燕、于亚新等针对数据流上近似查询中的梗概计算，提出 了一种新的基于最小误差的维压缩小波变换算法( m e d c ) 嘲。另外复旦大学的研究主要集中在流数据 的管理和分析方面p j ，中科院计算机技术研究所正试图构建一个面向网络信息安全的数据流计算模 型i s ，主要研究网络数据流的获取、建模、查询模型和计算方法等 对数据流的查询和聚类( c l u s t e r i n g ) 分析是近年来研究的一个趋势州。d a t a 一1 川通过对已见数据部 分( s l i d i n g w i n d o w ) 进行摘要处理来进行数据流挖掘，b a b c o c k o l 纽过先对直方图的每个“桶”( b u c k e t ) 进行分级聚类，然后用汇总的方法来研究数据流g i l b e r t i ”l 等一些学者则利用小波的技术对数据流 兰州大学硕士学位论文基于反馈机制的流数据查询 进行挖掘。“决策树” 1 3 1 ( d e c i s i o n t r e e ) 挖掘算法有着很广泛的应用，研究也很透彻，在此基础上进行 数据流处理将取得很好的效果 a u r o r a 2 4 等查询系统在数据流的查询方面做得较好，有五个方面与其他同类数据流处理系统有 着显著的差别，分别是面向工作流的方式、包含组新颖独创的操作符、着眼于有效的调度、着眼 于对服务质量最大程度的保证，以及对优化结构的显著改善。 决策树算法和数据流查询系统基本可以适应数据流查询处理的需求，但是仍存在以下一些问题： ( 1 ) 传统的决策树算法虽已成熟，但要在数据流中的动态应用需要进行改进 ( 2 ) 大部分查询系统的负载控制策略还不是很合理，比如a u r o r a 系统采用周期性更新负载卸载 路径映射的方法就存在着系统资源浪费。 ( a ) 大多数的查询处理系统没有对输出的具有很高参考价值的结果数据流加以重新利用，查询准 确度仍然有可以提高的空阅 1 2 研究内容 目前的流数据查询基本上都是只考虑对数据流当前数据的查询，对查询过的数据和输出的结果 流简单的加以存储，并未充分的利用起来。鉴于此，本文构造了一种基于反馈机制的流数据查询模 型，并对此模型及其关键技术进行了重点研究。 本文的主要研究内容有： 分析了目前存在的多种数据流处理的应用理论和技术，并总结了它们的优缺点 在分析其它实时数据流处理技术的基础上，构造了基于反馈机制的数据流查询处理模型， 并对其进行了深入的研究 在对a u r o r a 的负载卸载分析的基础上设计了基于反馈机制流数据查询模型中完备l s r m 的构建方法和基于自适应构建l s r m 的负载卸载算法。在数据流查询中设计了基于时闻粒 度的多层次滑动窗口，并对窗口的维护进行了详细描述，使数据流的查询处理能够在多层 次的滑动窗口上进行，提高了查询的准确度。 在决策树分类的基础上设计了基于反馈机制流数据查询模型中数据流的反馈树分类的生 长算法和剪枝算法，并分析了其有效性，有利于数据流查询精度的提高和系统处理数据流 性能的提升 2 兰州大学硕士学位论文 基于反馈机制的流数据查询 1 3 本文组织结构 本文的组织结构是这样安捧的： 第一章为绪论，讨论了本文的研究背景、研究内容及主要工作 第二章介绍了流数据查询的相关理论和技术 第三章构建了一个基于反馈机制的流数据查询模型并对其各部分的功能结构进行了阐述 第四章对基于反馈机制的流数据查询模型中的过载控制进行了详细的研究讨论，针对a u r o r a 系 统的负载卸载的不足之处提出了改进的方法。 第五章详细介绍了时间多粒度层次滑动窗口划分和动态的维护机制，并设计了数据流的连续查 询方案 第六章中将决策树演化为反馈树，并将反馈树的生长和剪枝方法进行了设计。 第七章对全文的工作进行了总结，并对下一步的工作进行了展望。 3 兰州大学硕士学位论文基于反馈机制的流数据查询 第二章流数据查询的相关理论与技术 数据流是最近很多应用中的数据所表现出来的种快速的有序地流的形式，流数据的查询就是 在这种数据形式上的一种数据操作，通过对流数据的查询，可以满足当前许多应用中的需求。 2 1 数据流 ( 1 ) 数据流的概念 数据流是一个实时的、连续的、潜在无界的、有序的( 隐含的通过到达时间或者明确的时间戳) 项的序列。因特网、w g b 应用以及传感器网络等已经促使应用将数据看作一种连续的数据流，而不 是固定的数据集合。 ( 2 ) 数据流的基本特点 数据流具有如下几个主要特点： 数据流的数据元素是连续在线式更新的，不能对其进行随机访剐1 4 1 。 数据流的实时特性决定了处理的结果会随着新数据的到达而更新，即处理结果能反映数据流 的整体情况。 数据流到达的顺序是无法控制的， 数据流在某种意义上讲是无界的【1 埘 数据流对数据结构的表示要求更高。不但要包含传统的基本数据类型，如整型、实型、字符 串等，还应包含更复杂的构造数据类型，如集合、递归结构及抽象数据类型等。数据对象之问存在 复杂联系，比如n 元联系、与时间有关的多类型多语义联系等。实时数据流处理除了能表示一般的 结构化、格式化的数据，还要能表示非结构、半结构化的数据” 数据流应用中的数据本身也表现出了与传统应用数据的不同特性；每一数据对象不再唯一由 其值来表示，每个值都有一个与之关联的时间，即数据是二维的( 值、时间) ，更进一步，也可能是 多维的；数据对象频繁地动态变化，变化的不仅有数据值，数据的定义( 如：类型、联系、构造等) 也动态改变；数据对象不单是传统意义下的“值”，还可能是过程、规则、方法、模型，也可能是声 音、影像或图像等 实时数据流处理中数据的使用也表现了许多特性，对流数据的操作，不仅能进行通常的插入、 删除，修改、查询等，还要能进行时态查询、构造操作和用户自定义操作等；传统的数据使用是单 4 兰州大学硕士学位论文基于反馈机制的流数据查询 向的被动存取，而数据流应用中的数据使用具有双向性，即数据的状态或状态改变可主动地驱动操 作的进行，数据流应用需要数据的状态( 值) 和模式( 定义) 的变化记录，即要求数据的多版本。 数据的准确性，在数据流应用中，数据的正确性不仅与数据的属性值有关，而且与属性值产 生的时间有关，即数据在此时刻是准确的，过段时间后可能就会不准确，即数据有数据值和时间上 的二维准确性 ( 3 ) 数据流处理的要求 根据以上特点，数据流处理应该满足以下要求：用有限来表示无限同时处理大量数据是非 常困难的，处理几乎接近无限的数据更是不现实的，应该采取一种把无限数据集映射到有限数据集 的方式进行处理能够增量式地维护。在实时的动态情况下，流数据是不断更新的。因此，在有 限的主存中需要维持一定数量的摘要信息，并根据一定的更新机制，进行实时的更新和维护i i 司。 ( 4 ) 数据流处理的操作特性【1 9 1 在不同领域应用中的数据流处理模型可能会有不同的特征、要求和限制，与传统的数据库处理 系统相比，实时数据流处理模型的处理操作应有以下的基本特征： 时效性 不仅要及时处理流数据的“当前”值还要对其变化的历史数据进行处理；流中的数据一旦经 过处理，要么被丢弃，要么被归档存储，但被丢弃的数据元素可能需要再次被访问。 复杂性 数据流的处理操作复杂，不仅包括传统的查询、插入、删除、修改等操作。还应有对时间戳的 处理以及用户自定义的操作等；对实时数据流处理的操作处理不仅要考虑处理后逻辑结果的准确性， 还要考虑处理产生的结果在时间上是否合乎处理的需求 单向性 在许多基于时间关键性实时处理模型中，处理过程是不可还原和重现的，由于处理的连续性， 即使能进行还原和重现，对于应用来说毫无实际意义。 协作性 各处理事务的执行不是独立的，它们在语义结构、数据，操作、时间等方面有相互依赖性他 们之间有着数据或逻辑上的联系。 2 2 滑动窗口技术 在处理持续到达的数据流时，通常并不是对所有已经到达的数据都感兴趣，而是只对最近到达 的部分数据感兴趣，这就需要引入窗口模型1 2 0 - 2 1 。定义窗口语义是数据流处理中非常基础性的工作， 5 兰州大学硕士学位论文 基于反馈机制的流数据查询 直接关系到数据流的存储和查询的执行效率。 数据流实时处理存在两种比较流行的窗口模型：箭标窗口和滑动窗e l p 3 。一般窗口都有两个端 点，分别确定这个窗1 3 的起始位置和终止位置，箭标窗口的一端是固定的，另一端随着数据流新元 组的到达向前移动。滑动窗口则与之相反，窗1 3 的两端随着新元组的到达而同向移动。本文中使用 的是滑动窗1 2 1 模型滑动窗1 3 随着元组的到达不断向前滑动，滑动又分为跳动窗1 3 和滚动窗口 跳动窗口是每到达一个新的元组。窗口跟着向前滑动一个位置；假定滑动窗口容量大小t 为4 元组，如果每当n ( r l s t ) 个元组到达时，窗口才向前滑动1 1 个位置的滑动窗口图2 - 1 所示为t - - 4 ，i 产2 时跳动窗口的倒子 到达时间5 0 1 0 05 0 1 1 05 0 1 2 0 5 0 1 3 0 3 0 2 0 0 3 0 2 4 03 0 3 5 53 0 4 5 03 0 6 3 5 数据值 亘至 i ! 至匡】二垂三 至亟二 歪垂至i 三至至 二垂虿 1 至三工回 藤瀚圈匣垂鬻缀凝黧 戳滋谶灏叵巫凰豳 圈2 1t - - - - 4 ，l l = 2 时的跳动窗口 滚动窗口是每到达一定数目的元组时窗口才向前滑动窗口大小t 个位置的滑动窗口，即如果每 当m ( 衅吣个元组到达时，滑动窗口向前滑动t 个位置。这样的窗口被称为滚动窗口当跳动窗口的 n - - t 时，就成为m - - t 的滚动窗口图2 - 2 为停4 ，m = 4 滚动窗口的例子 到达时间5 0 1 0 05 0 1 1 0 5 0 1 2 05 0 1 3 03 0 2 0 0 3 0 2 4 03 0 3 5 53 0 4 5 0 3 0 6 3 5 数据值 亘亘 重亘互工j 至 工 匝互】j 茧亘 二豆歪 二圣至二 亘至 固 懿露旺圈躐戮翻豳 图2 2t - - 4 ，m - = 4 时的跳动窗口 2 3a u r o r a 系统 2 3 1a u r o r a 系统概述 a m o r a 系统1 2 4 i 是由b r o w n 大学和b r a n d e i s 大学联合发起的一个项目此项目的主要目的是实现 一个单机的高性能流数据处理引擎。a u r o r a 系统包含一组独刨的操作符( o p c r a t o r s ) ，面向工作流执行 任务。它着眼于尽量提高系统所面向的应用的服务质量。a u r o r a 项目的后续目标是将其处理引擎进 一步扩展，从而应用于分布式环境，使得多台机器可以紧密、良好地协作来完成高质量的服务 a u r o r a 的工作流是动态的。形式是“盒子箭头”，当新的应用连接到工作流后，盒子和箭头都 会变动。盒子是一系列的操作符，箭头代表数据的流动方向如图2 - 3 所示为a u r o r a 系统模型图， 6 兰州大学硕士学位论文基于反馈机制的流数据查询 图中的o p l ，o p 2 等就是含有处理操作符的“盒子”。 图2 - 3a u r o r a 系统模型嗣 a u r o r a 系统采用的是一种局部最优的策略，可能做不到全局最优，当工作流过于庞大时，不能 保证得到的是全局最优的结果。对于非常大的数据流目前还没有更好的解决办法 2 3 2a u r o r a 系统的负载卸载 图2 - 4 显示了a u r o r a 系统的负载卸载基本流程，从图中可以看出系统监控数据流的输入流率， 进行工作量检查，当工作量超过系统的性能许可时，即工作l t h l * c 时，负载卸载器查找负载卸载 路径映射( l s r m ) ，从中得到一个丢弃操作插入计划，即确定在查询网络中插入丢弃操作符的位置 信息同时系统对l s r m 进行重新构建，形成能反映新情况的负载卸载路径映射 图2 - 4 a u r o r a 系统的负载卸载基本流程图刚 7 兰州大学硕士学位论文 基于反馈机制的流数据查询 a u r o m 的负载卸载是间断性的进行的，重建负载卸载路径映射( l s r m ) 是周期进行的，这种 l s r m 的重建有以下缺点：系统不过载的时候没必要进行负载卸载。假如l s r m 没有发生改变， 就没有必要重建l s r m 。重建l s r m 的周期的确定中是一个难题本文第四章对其进行了改进 2 4 决策树分类算法 在本文设计的反馈机制中需要借助决策树分类算法对查询结果进行分类，下面简要介绍决策树 分类算法f 1 3 j ， ( 1 ) 决策树的概念 决策树是一个类似流程图的树结构，其中每个内部结点代表在一个属性上的测试，每个分技代 表一个测试输出，而每个树叶结点代表类或类分布 ( 2 ) 决策树分类模型 决策树分类的过程是对训练集采用一定算法构造决策树的过程，其模型如图2 - 5 所示： ( 3 ) 决策树分类的基本算法 决策树分类算法主要分成两个步骤：首先，树的生成开始，即数据都在根节点递归的进行数据 分类。其次，树的修剪，即去掉一些可能是噪音或者异常的数据。 决策树生成 决策树生成的基本算法思想为。自上而下分而治之的方法开始时，所有的数据都在根节点，属 性都是种类字段( 如果是连续的，将其离散化) ，所有记录用所选属性递归的进行分割，属性的选择 是基于个启发式规则或者一个统计的度量( 如，i n f o r m a t i o ng a i n ) 。停止分割的条件是一个节点上的 数据都是属于同一个类别没有属性可以再用于对数据进行分割 。 决策树生成的基本算法的伪代码如下； b u i l d t r e e ( s ) i n i t _ r o o t ( s ) ； 用数据集s 初始化根节点r o o t i n i t _ q u e u e ( r o o t )用根结点r 初始化队列q u e u e 8 兰州大学硕士学位论文 基于反馈机制的流数据查询 w h i l e q i s n o t e m p t y d o n 6 - t a k c _ d a t a ( q ) ；取出队列q 中的第一个节点赋给n i f n o t 印唧n ) 对每个节点n 每个属性a 计算其信息增益 f o re a c h a c o m p u t eg a i n ( n a ) s e l e c to p t i m a l ( n ) o ，选择最优分类属性进行分割 o a s s i f y ( n ) ； 树的修剪 树修剪目的是消除决策树的过适应( o v e rf i a i n g ) f 司m ，实质是消除训练集中的异常和噪声常 用的两种剪枝标准分别是最小描述长度原则m m 如；m l 珊d e s c r i p t i o nl e n g t h ) 和期望错误率最小 原则。 m d l 原则的做法是对决策树进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”； 期望错误率最小原则是选择期望错误率最小的予树进行剪枝，对树中的内部节点计算其剪枕怀剪枝 可能出现的期望错误率，比较后加以取舍。 目前决策树算法正被移植到数据流应用中，文献0 5 1 给出了决镱树解决许多问题的介绍。同时重 点介绍了决策树的c a 5 算法，决策树算法包括c a 5 的前驱i d 3 ( q u i n l a n ) ，c a r t ( b r e i m a n ，f r i e d m a n ， o l s h e n s t o n e ) ，f a c t 0 o h 和v a 面c h s e t a k u l ) 。p u b l i c 承a s t p g i 和s h i m ) ，c h a m 妒1 1 i ) 3 的增量版本包括i d 4 ( s d d i m m c rf i s h e r ) 和i d 5 ( u t g o p 2 3 s l 。此外，i n f e r u l e ( u t h u r u s a m y ，f a y y a d 和s p a i l g i 砷由非决定数据的学习来构造决策树洲：配u 日m 跚4 驴和k o d 咖毋由复杂的结构化数据 学习构造决策树嗍；强调在数据挖掘中可伸缩性的决策树算法包括s l i q ( m c h t a , a g r a w a o ， s p r i n t ( s h a f e r , a g r a w a l ) 、雨林抛如嗡r a m a “s h n a n ) 、b o a t ( o e h r k e ，g a 埘) i 等p 甜卵s l i q s p i t i n t 算法使用预排序技术以及新的数据结构，大大提高了对于大规模数据集的可扩展性【批蜘 9 兰州大学硕士学位论文基于反馈机制的流数据查询 2 5 过载卸载技术概念 本文的数据流查询处理中设计了一种基于a u r o r a 系统的改进的负载卸载策略，首先介绍传统卸 载策略【1 1 的概念及原理 ( 1 ) 基本概念 过载：指由于数据流经常是爆发性的并且数据特征可能随时变化。当输入流速超过系统处理 能力时，系统处于过载状况 卸载：当系统产生过载且性能下降时，可以通过增加更多的处理资源或将计算分布到多个节 点上，但这种方法在经济上可能是不可行的。另外种行之有效的方法是卸载，即丢掉部分尚未处 理的数据，以便使系统减轻负载，恢复正常工作 ( 2 潆统的卸载技术 卸载处理是要丢掉部分尚未处理的数据，主要应考虑以下三个关键问题t 卸载时间。必须对查询系统的负载处理情况进行连续的评估，应能及时检测到系统存在的超 载情况，并且实施卸载 卸载地点。在处理系统的任意点均可以丢弃元组。显而易见，尽量早地丢弃元组可以避免多 余的工作。但同时应注意，如果存在一个流扇出为多个流的情况，被过早丢掉的元组会对多个应用 产生不利的影响 卸载数量。一旦确定了插入丢弃( d r o p ) 操作符的位置接下来应该决定卸载的数量。在随机丢 弃的情况下。应考虑丢弃元组的百分比 目前卸载主要通过两种方法来实现，即随机丢弃( 姐l i d 帆d m p ) 【4 2 j 和语义丢弃 删邱d r o p ) 1 + 3 1 1 0 兰州大学硕士学位论文 基于反馈机4 的斑数据查询 第三章基于反馈机制的流数据查询模型的构建 多数的数据流查询处理系统都是一种被动的查询机制，对当前数据流进行处理后，只是将输出 结果流反馈给用户或输出到存储设备，未充分利用已得到的输出结果数据流。而输出结果流对连续 查询处理具有很高的参考价值，本章主要构建了基于反馈机制的流数据查询模型，并对其主要部分 作了介绍 3 1 基于反馈机制的数据流查询模型 在传统的数据流查询的基础上，将反馈机制引入数据流查询模型中，此机制查询数据流的核心 问题以下三个：数据流到来时，如何对数据的到来速度进行控制使数据流到来速率较高时仍能实时 查询数据流即过载控制；其次，对其中数据序列进行管理并根据用户的查询需求进行查询；最后， 对查询处理的结果流进行反馈树分类，形成与处理数据流特征基本符合的相的反馈表来指导系统中 的过载控制和查询处理。基于此分祈，可以构建基于反馈机制的数据流查询模型如图3 - i 所示： 图3 1 基于反馈机制的数据流查询模型 从图3 1 可以看出该模型主要分3 个部分：过载控制，查询处理和反馈生成。以下对这几部分 进行详细阐述。 i i 兰州大学硕士学位论文基于反馈机制的流数据查询 3 2 过载控制 3 2 1 循环缓存数据流 数据流的临时数据区采用循环缓冲处理技术， 使用较小量的内存可以采集到几乎无限多的数据。 如果系统性能与数据流的速度基本匹配，就可以 系统接收数据流的输入数据，缓存到一个输入缓 冲区中，用于缓存数据流数据的缓冲区在逻辑上被分为几个完全相等的部分( 具体的数目在不同的应 用中有所不同) ，每一部分称之为缓冲池，这里为了说明方便，我们将缓存区分为2 个缓冲池。 系统开始工作时首先将流入到查询系统的数据写入第一个缓冲池中，在开始向第二个缓冲池中 写入数据的同时，数据流处理程序可以根据需要对第一个缓冲池中的数据傲特定的处理，比如划分 滑动窗口。数据流的查询等；在第二个缓冲池被写满之后，数据接收器将返回到第一个缓冲池的起 始处，用覆盖前次数据的方式，把数据写入第一个缓冲池中。整个数据收集处理的过程可以如此不 断地循环进行下去 3 2 2 过载卸载 由于数据流具有随时问动态变化的趋势，随时间变化不可预测，当数据流到达的速率不易被处 理系统所控制时就需要对数据流进行过载控制，来保证系统对数据流查询处理跟的上数据流的变化 本文中谈到的过载控制部分是一个运行在查询网络的c p u 的连续的监控器，查询网终的结构及 构成如图3 - 2 所示。当检测到过载时，丢弃操作器被插入到查询网络的某一查询操作之前，通过丢 弃部分元组操作点的查询数据量来提升系统性能。 负载卸载器l s r m 维护器 气，二，7 。 l。7 l 负载降载路径映射 l s r m 丢彝插入 计划 图3 - 2 负载卸载的模型 兰州大学硕士学位论文基于反馈机制的流数据查询 系统即时监控数据流的输入率、查询系统的工作量，当数据流的输入速率到达一个阈值时，也 就是查询系统的工作量超出系统的处理能力时系统调用负载卸载器从负载卸载路径映射l s r m 查 找到丢弃插入计划，根据计划将丢弃操作符插入到查询网络，丢弃插入点处数据流的部分元组，同 时由负载卸载路径映射维护嚣对l s r m 进行维护更新。 本文将在第四章中详细阐述负载卸载的处理方法 3 3 基于，时问粒度分层滑动窗口的查询处理概述 关于时间t - 粒度的滑动窗口技术将在第五章进行详细的阐述，这里主要介绍一下查询的基本模 型结构，如图3 - 3 表示。 图3 _ 3 数据流查询的基本模型结构 数据以数据流的形式到达系统，由窗口管理在流中动态选取数据行插入到“近期数据”视图中。 其中，窗口管理器以及图3 - 3 中的所有其它模块都将会对元数据进行访问。 “近期数据”的数据会过期。数据过期时，或者在某个更合适的时候( 比如在系统负载较轻时) ， 数据转存把过期数据从“近期数据”视图中清除，同时把它们插入“历史数据”视图中。可能某个 时刻会在这两个视图中存在冗余数据通过这种机制，查询总是可以得到需要的数据。 普通的即时查询通过即时查询处理器来处理而连续查询由连续查询处理器来进行即时查询 将被分解成分别针对“近期数据”和“历史数据“的子查询，然后产生一个数据流上的概要数据结 构，并同时把查询送往连续查询处理器，从而在查询结果变更时可以相应的进行更新对于连续查 询，需要数据流概要信息来维护数据流的中间状态和查询结果，针对近期数据得到不断更新的查询 结果。当查询被取消时，连续查询处理器得到通知然后停止更新概要信息。具体的连续查询过程将 在第五章详细介绍 1 3 兰州大学硬士学位论文 基于反馈机制的流数据查询 3 4 基于反馈树的反馈生成概述 本文采用了决策树的一些概念和方法，采用了树形结构动态的对结果数据流中数据进行维护处 理，在树的节点上增加了流数据的一些特有属性比如时问戳属性等和能反映数据流特征的反馈系数 属性，本文中将这种树型结构称之为反馈树 在反馈生成部分接收到结果数据流的输入数据时，对数据流进行反馈树分类，分类过程中的决 策树生长和剪枝过程中对非叶子节点进行反馈度属性的即时计算更新 定期的从生成的反馈树结构中提取出具有较高参考价值的反馈参数，本文采用了层次遍历反馈 树的提取中问层反馈度系数，关于层次遍历反馈树的算法详见文献m 。 利用哈希函数即l 将其映射到反馈参数表中反馈生成的模型如图3 4 所示； i 反馈树生长l 叫般肭皴fl 睁参数表i l 反馈树剪枝i 3 5 小结 图3 - 4 反馈生成模型 在本章中，构建了一个基于反馈机制的流数据查询模型，此模型在对查询结果流进行进一步加 工处理后生成具有反馈参数的反馈树，这些参数可以反映查询结果数据流特性，即这些参数就是查 询计划在输入数据流中的表现，所以用这些特征参数指导数据流的实时查询及其相关处理，可以进 一步优化查询的处理，提高查询的准确度将特征参数反馈到数据流的过载控制中，在过载控制时 参考这些参数，也可以提高查询的准确性 1 4 兰州大学硕士学位论文 基于反馈机制的流数据查询 第四章过载控制 根据3 2 的过载控制的过程，本章将详细介绍过载控制中的过载卸载这一关键技术本章的工 作是在a u r o mi “】数据流处理架构基础上的负载卸载的研究，负载卸载器的功能和构造同a u r o r a 基 本一致在负载卸载路径( l s r m ) 的构建上提出了改进的完备负载卸载路径映射皿s i t 的构建方法 和自适应的负载卸载路径映射的构建方法。 为了描述向题的方便首先给出一些相关定义： 系统性能：系统每秒钟可以承受的c p u 周期，单位周期，秒； 工作量：当前输入的每秒时间的c p u 周期，单位周期缈； 过载量：过载量；工作量- h * 系统性能 常数h 是系统稳定状态下处理数据流所需要系统资源的百分比估计，般情况下h 值默认为是 o 9 l “1 4 1 过载卸载的基本模型结构 负载卸载模型主要包含3 个组成部分，负载卸载器和负载卸载路径映射s r m ) 维护器，和使用 到的重要数据存储结构负载卸载路径映射( l s r m ) 附载卸载的基本框架图如图4 1 所示： 数据流查询网络 图4 - 1 负载卸载的模型 兰州大学硬士学位论文基于反馈机制的流数据查询 4 2 负载降载路径映射 过载控制中的负载降载路径映射负载降载路径映射o 暑l 是一个查询入口的有序序列，格式 为： 周期节省系数( c s c ) ，丢弃插入计划，当前提交指针c p 负载降载路径映射的存储形式如图4 - 2 所示： 周期节省系数( c s c ： 丢弃插入计划( d i p ) o o s 指针( p d c ) j c l 罐 p l c 2p 2 c 3 雹忙h ) 口 p 3 j c l 固h ) 口 p 1 晓 葚k 血) 口 p 2 c 3 翟k h ) 口 p 3 图4 2 降载路径映射( l s r m ) 州 丢弃插入计划( d i p ) 是一个将要在查询网络插入丢弃操作符的箭头的集合，周期节省系数可 以确定如果对应的丢弃插入计划( d i p ) 被采用，将插入丢弃计划位置的数据推进到输出共节省多 少个c p u 周期百分比提交指针( p d c ) 指向此查询结果的服务质量表q o s 。 4 2 1l s r m 的构造 负载卸载路径映射l s r m 在整个负载卸载中具有重要的作用，首先来讨论l s r m 的构造过程， 本文的l s r m 构造过程如下： 步骤l ：找到可能的丢弃插入点 既然负载卸载的目标是使查询精度的损失达最小，建立一个新的l s r m 入口时，插入丢弃操作 符的最好的点是有最小的l o s d g a i 豹比率的位置f “l 。一个查询计划未共享其他的查询计划时，则 丢弃操作符尽可能选择较早的位置为丢弃操作符的插入点 步骤2 ：分配负载系致 每个操作盒子”都带有系统开销( 周期每秒) 和选择度，可以计算每个箭头上的负载系数1 3 9 1 。 用负载系数l ( 周期，元组) 乘以流率r ( 元组缈) 就可以得到每个插入位置的工作量w o r k l o a d ( 周期 1 6 兰州大学硕士学位论文 基于反馈机钊的流散据查询 每秒) 即 worldoad=-lr(扣1) 丢弃操作符位于在高负载系数位置就意味着此位置丢弃一个元组将会得到更多的c p u 周期 步骤4 ：为各可能插入点分配q o s 图表 图4 3 是一个为查询网络的丢弃操作符插入点分配o o s 图的例子，其中的虚线箭头表示q o s 的 分配方向，由于b ，d ，f 分别仅仅影响o l ，0 2 ，0 3 ，所以b ，d ，f 位置的q o s 图分别与0 1 ， 0 2 ，0 3 处的q o s 图完全一样。然而由于在a 位置放置丢弃操作符将会影响o l 和0 2 的结果，所 以a 处的q o s 图可以通过b 和d 处的q o s 图的函数相加得到。 图4 - 3 为丢弃插入位置分配q o s 图的例子 步骤5 ：监控输入率 尽管可以得到所有可能的丢弃位置的负载系数和q o s 图的信息，但仍不知道每一个输入流的输 入率。输入数据流的输入率只能通过监控输入流而得到，因此对每一个可能的丢弃插入点来说计算 l o s s g a i n 比率时，输入率是仅有的变量，其他的参数都是静态可计算的常量 步骤6 ；计算可能的丢弃操作符插入点的l o s s g a i n 值 l o s s g a i n 比率的计算公式m 如下所示： 翼堂壅挲( 4 - 2 ) k l 1 l o s s 是每个可能的丢弃插入点的q o s 图的曲线的斜率，即u 伍) 的负斜率，g a i n 表示那个丢弃 点位置丢弃1 的元组所获得的每秒c p u 周期数。可以用。r x l x1 ”来计算。 1 7 兰州大学硕士学位论文基于反馈机制的流数据查询 将所有的l o s s g a i n 比率计算并按升序排列，进行l s r m 格式存储，至此l s r m 构建基本完成。 l s r m 构建的基本过程如图4 - 4 所示： 4 2 2l s r m 的使用 图4 - 4l s r m 的构建过程州 根据系统的工作量超过保持系统稳定性能的差值来查找负载卸载路径映射l s r m ，从中找到第 一个能够卸载这个差额负载的丢弃插入计划。 节省周期系数( c s c )丢弃插入计划( d i p ) q o s