（计算机应用技术专业论文）基于数据流的聚合函数精确计算研究及其应用.pdf

摘要 摘要 随着网络的不断普及，流数据处理逐渐受到关注，流数据中的聚合计算也越来越 重要。在传统数据库管理系统中，聚合函数定义为对一组值进行计算，并返回单个值 的函数。在本文的研究中，我们仍然使用该定义。解决数据流中的聚合函数计算问题， 对处理数据流，解决网络中的监控、统计、检测等问题具有现实意义。 本文主要贡献如下： ( 1 ) 对输入数据的类型为数值型的聚合函数，提出了一种存储最少数据的m a x 函数和m i n 函数的精确计算方法。这种方法是一种基于数据流滑动窗口聚合函数的 精确增量式计算方法，它对于长度为n 的输入序列，算法的时间复杂度为o ( n ) ；最 坏情况下，空间复杂度为0 ( ) ，最好情况下，复杂度为d ( m ) ，其中，m 为预先分 配内存的大小。并通过数学理论分析和证明了该方法的正确性，还通过实验检验了该 方法的有效性和实用性。最后还实现了c o u n t 、s u m 、a v g 、s t d e v 、s t d e p 、v a r 、 v a r p 等聚合函数的计算方法增量式计算方法。 ( 2 ) 对输入数据的类型为字符型的聚合函数，实现了一种基于通用后缀树( g s t ) 表示的字符串频率统计方法。该方法不需要任何训练，直接对接收的文本进行统计， 并根据字符串的频率进行分类；对于长度为n 的文本，算法的时间复杂度和空间复杂 度均为0 ( ) 。并应用对输入数据的类型为字符型的聚合函数的精确计算方法实现了 一种基于后缀树的骨干网络垃圾邮件检测方法。该检测方法采用通用后缀树( g s t ) 表示邮件文本；当新的邮件到达时，通过不定长统计方法计算该邮件和其他类别邮件 的相似废，并确定邮件所属类别，然后利用聚合函数统计邮件重复出现的次数，最后 判定该邮件是否为垃圾邮件。理论分析和实验表明该检测方法具有以下特点： 该方法充分利用了骨干网络的信息量大等特点，适合于骨干网络或大型服务 器的垃圾邮件检测； 该方法独立于任何语种，适用于多语种邮件同时存在的情况。 关键字：数据流，聚合函数，精确计算，后缀树，垃圾邮件检测 第l 页 a b s t r a c t t h es t u d yo f a ne x a c ta g g r e g a t i o nm e t h o db a s e do nd a t as t r e a m a n di t sa p p l i c a t i o n z h e n gy a o d o n g ，c a p i t a ln o r m a lu n i v e r s i t y & i n s t i t u t eo fc o m p u t i n gt e c h n o l o g y , c h i n e s ea c a d e m yo fs c i e n c e s ，j o i n tf a c u l t yo fc o m p u t e rs c i e n t i f i cr e s e a r c hi n s t i t u t eo f c o m p u t m gt e c h n o l o g y d i r e c t e db yg u ol i 、l i uj i n g a n g a b s t r a c t w i t ht h e p o p u l a r i t y o fi n t e r a c t ，m o r ea n dm o r e p e o p l ep a y a t t e n t i o nt ot h e m a n a g e m e n to fd a t as t r e a m i ti sm o r ei m p o r t a n tt oc a l c u l a t ea g g r e g a t ef u n c t i o n si nd a t a s t r e a m i nd a t a b a s em a n a g e m e n ts y s t e m ，a na g g r e g a t ef u n c t i o ni sd e f m e daf u n c t i o nt h a t r e t u r n sas i n g l er e s u l tt h r o u g hc a l c u l a t i n gag r o u po fv a l u e s i nt l l i sp a p e r , w es t i l lm a d eu s e o ft h ed e f i n i t i o n r e s o l v i n gc a l c u l a t i o no fa g g r e g a t ef u n c t i o n si nd a t as t r e a mh a sm e a n i n g r e a l i s mf o rm o n i t o r i n g ，c o u n t i n g ，d e t e c t i n gd a t as t r e a ma n dn e t w o r k t h em a i nc o n t r i b u t i o no f t h i sp a p e ri sa sf o l l o w ： ( 1 ) w h i l et h ed a t at y p eo fi n p u td a t ai san u m e r i c mt y p e ，t h i sp a p e rp r o p o s e dan e w e x a c ta g g r e g a t i o nm e t h o da sl i t t l ea sp o s s i b l es t o r e dh i s t o r i c a ld a t af o rt h em a xf u n c t i o na n d t h em i nf u n c t i o n t h i sm e t h o di sa ni n c r e m e n t l yc a l c u l a t i o n a lm e t h o db a s e do ns l i d i n g w i n d w o so fd a t as t r e a m i tt o o ko ( ) t i m et od e a lw i t ha ni n p u td a t al i s to fl e n g t hn i t t o o kd ( ) s p a c eu n d e rt h ew o r s tc i r c u m s t a n c e so rd ( m ) ( i tp r e a s s i g n e dmb m e m o r y ) s p a c eu n d e rt h eb e s tc i r c u m s t a n c e st od e a lw i t i la l li n p u td a t al i s to fl e n g t hn a n dw e a n a l y z e da n dp r o o f e dt h en e wm e t h o dt h r o u g hm a t h e m a t i ct h e o r y m o r e o v e r , w ec h e c k e d t h en e wm e t h o db ys o m ee x p e r i m e n t s a tl a s t , w er e a l i z e da l le x a c ta g g r e g a t i o nm e t h o d - - a ni n c r e m e n t l yc a l c u l a t i o n a lm e t h o do fa g g r e g a t ef u n c t i o n s ，f o re x a m p l ec o u n t ，s u m ，a v g ， s t d e v , s t d e p ，v a l , a v r p ( 2 ) w h i l et h ed a t at y p eo fi n p u td a t ai sas t r i n gt y p e ，t h i sp a p e rr e a l i z e das t a t i s t i c a l m e t h o db a s e do ng e n e r a lg e n e r a ls u f f i xt r e em o d e lf o rf r e q u e n ts t r i n g t h i sm e t h o dd i d n l t r e q u i r ea n yt r a i n i n gc o r p u s ，a n dd i r e c t l yc l a s s i f y i n ga n dc o u n t i n ga c c e p t e dt e x t st h r o u g h t f r e q u e n ts t r i n g i tt o o k0 ( ) t i m ea n d0 ( ) s p a c et od e a lw i t ht h et e x to rs t r i n go f l e n g t hn a n dt h i sp a p e rr e a l i z e dan e ws p a r ed e t e c t i o nm e t h o do nb a c k b o n en e t w o r k t h r o u g ht h ee x a c ta g g r e g a t i o nm e t h o df o ri n p u td a t at h a tb e l o n gt ot h es t r i n gt y p e t h i s m e t h o dr e p r e s e n t e dt h et e x to fe m a i lw i t hg e n e r a ls u f f i xt r e es t r u c t u r e a n dw h e nan e w 第1 i l 页 基于数据流的聚台函数精确计算研究及其应用郑耀东 m a i la r r i v e di n ，i tu s e dt h ev a r i a b l el e n g t hs t r i n gm a t c h i n gm e t h o dt od e c i d et h es i m i l a r i t y b e t w e e nm a i l s ，t h e nu s e dt h ec o u n to fs i m i l a rm a i l st od e t e r m i n ew h e t h e rm a i l sa r ej u n k m a i l so rn o t t h ea d v a n t a g eo ft h i sm e t h o di n d i c a t e dt h r o u 【g ht h e o r ya n de x p e r i m e n ti sa s f o l l o w ： t 1 i sm e t h o dm a k e sg o o du s eo f al o to f i n f o r m a t i o no f b a c k b o n en e t w o r k 。a n di ti s f i tf o rd e t e c t i n gs p a m so nb a c k b o n en e t w o r ko rs e r v e r t h ec a t e g o r i z i n gm a i l si si r r e l e v a n tt od ow i mt h ec o n c r e t el a n g u a g ea n di sa l a n g u a g ei n d e p e n d e n tm e t h o d k e y w o r d ： d a t as t r e a m ，a g g r e g a t ef u n c t i o n ，e x a c tc a l c u l a t i o n ，s u f f i xt r e e ，s p a md e t e c t i n g 第页 图目录 图1 1 图2 1 图2 2 图2 3 图3 1 图3 2 图3 3 图3 4 图3 - 5 图3 6 图3 7 图3 _ 8 图3 - 9 图4 1 图4 2 图4 3 图4 - 4 图4 5 图4 6 图4 7 图目录 计算聚合函数的装置原理图5 滑动窗口和基本窗口之间的关系图7 在线聚合中a v g 聚合函数的某一个结果显示图1 1 在线聚合中a v g 聚合函数的多个结果显示图1 1 数据序列为x = x l ，x 2 ，x i ，x ，x 。的波形曲线 曲线y = f ( x ) 的示意图( 一) 一 曲线y = f ( x 1 的示意图( 二) 一 内存分配图( 一) 内存分配图( 二) 内存分配图( 三) 内存分配图( 四) 存储数据的最大数量m a xs t o r ec o u n t 的实验结果图 平均存储百分比a v gs t o r ep e r c e n t 的实验结果图 通用后缀树结构和类别统计结构 后缀树方法的分类实7 验结果 d b s d 方法的分类实验结果 后缀树方法的消耗时间实验结果 d b s d 方法的消耗时间实验结果 后缀树方法的检测垃圾邮件实验结果 d b s d 方法的检测垃圾邮件实验结果 第v i i 页 悖加孙弭拼巧筋玎”弘”强弘”们 苎三塾堡鎏塑墨皇里塑塑塑兰兰型窒墨些些里竺塑变 表目录 表3 1 参数t o t a l c o u n t 的值为1 0 0 0 0 时的实验结果 表4 1 实验的分类结果 表4 - 2 实验的性能及其对比 第v i i i 页 2 6 3 6 3 6 首都师范大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作：郇讯糸 首都师范大学位论文授权使用声明 日期：) 6 年4 月f 譬日 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位沦文的内容 编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文 在解密后适用本规定。 学位论文作者签名： 郑坦趸 日期：力岛年啦月2 日 第一章引言 1 1 应用背景 第一章引言 随着因特网在全世界的普及，网络传输技术的迅速发展，每天世界上有海量的各 种类型的信息在互联网上流动，比如文本信息、声音信息、图像信息等。信息的高速 增长迫切需要信息处理技术的不断进步。 根据数据的存在形态，一般可以将数据处理划分为两种对偶的形式：静态数据处 理和流动数据( 本文中，又称为数据流) 处理。静态数据处理以数据为中心，整个数 据集存储在一个庞大的、相对稳定的中央存储介质中，并随时准备接受随机到来的用 户数据请求。在数据集的生命周期，绝大部分数据是稳定不变的，而频繁变化的是用 户随时可能提交的查询。静态数据处理方式的典型应用包括：数据库管理系统、信息 检索系统、数据仓库系统等。长久以来，静态数据处理得到了广泛深入的研究。 流动数据处理以查询为中心，数据集仍然是庞大的，但具有高度的流动性。而相 对稳定的是用户查询，大量预先定义的用户查询被注册到处理系统中，等待数据的到 来。一旦数据到来，将驱动查询的执行。显然，数据密集的生产系统所产生的日志数 据，都具有这种海量且流动的特点，这样的系统包括：互联网管理系统、证券交易系 统、电信系统、金融交易系统，实时传感器信号分析系统等。这些应用面对的都是在 线的、持续的高速流数据，系统处理的对象形态完全不同于传统的静态数据处理，由 于存储空间的限制，这些数据往往不可能完全保存到存储器中，同时又必须不问断无 延迟地处理这些流数据，以获得实时处理结果。由此产生了一些新的基础性研究问题。 流数据是数据元素的有序序列，序列中的数据元素顺序到达流数据处理系统。在 某些具有并发性的应用环境下，流数据中的元素可能同时到达，我们把同时到达的元 素视为一个列表，那么可以把流数据建模为数据元素列表的序列。流数据处理系统的 输入数据并不保存在可随机访问的磁盘或主存中，输入数据以一种瞬态的、持续的流 的形式到达。概括来说，相对于传统数据库模型，流数据模型主要有如下几个方面的 特征： 流中的数据元素在线到达； 从理论上说，流数据的潜在大小是无限的；系统能存储的数据相对流数据的 大小则是非常有限的； 一旦流数据中的某个元素经过处理，要么被丢弃，要么被归档存储。但被丢 弃的数据元素可能需要再次被访问； 分析流数据元素的结构，从简单到复杂有这样几种： 第l 页 基十数据流的聚合函数精确计算研究及其应用 郑耀乐 不关心语义的字符流，这种流具有取值为字符的一维结构； 结构化流数据，这样的流数据的数据元素可以视为关系元组，关系具有固定 的域，因此这样的流数据具有二维结构，一维为元组序列，另一维为元组内 的域； 半结构化流数据，如x m l 文档流，这样的流数据中存在着用户定义的、具有 一定语义的标记，可用这些标记将流数据划分为独立的流数据元素； 无结构数据，如具有自描述结构的文本流，以及连续的视频流、音频流等， 这种流的结构信息完全包含在数据的语义中，无法孤立地对数据进行元素划 分。 流数据中聚合函数计算十分重要。如果用户查询( 或计算) 中包含聚合函数，且 该函数事先没有计算出结果，那么就必须要求对聚合函数进行现场计算。解决数据流 中的聚合函数计算问题，对处理数据流，解决网络中的监控、统计、检测等问题具有 现实意义，还可以解决以下一些典型应用中的聚合函数的计算问题。 ( 1 ) 证券、股票交易数据的实时处理：因为交易的数据都是在线实时产生，如 果用户需要及时获取交易的信息( 如股票价格) ，那么就必须要求在线实时处理( 或 计算) 这些交易数据，以满足用户的需求。 ( 2 ) 网络流量统计和监控：由于网络流量数据是在线、实时产生，为了对网络 流量进行统计和监控，因此必须实时处理( 或计算) 这些数据，如统计流量的最大值、 最小值，对流量进行排序等。 ( 3 ) 垃圾邮件检测和过滤：对于基于统计方法的垃圾邮件检测或过滤系统而言， 邮件数据的到达是随机的，为了及时把邮件提交给用户，系统必须及时处理到达的邮 件数据、计算出判定垃圾邮件所需要的信息。当到达的邮件数量很大时，这就要求系 统在足够短的时间内处理这些邮件。 根据计算结果是否精确这一个特点，可以把聚合函数的计算可以分为近似计算和 精确计算。近似计算是计算聚合函数的近似值，即计算结果和精确结果相比较，可能 存在一定的误差，是一个近似值。精确计算是计算聚合函数的精确值( 或精确解) ， 这是本文研究的主要内容。 1 2 数据流管理系统 国际上系统地进行数据流的研究开始于2 0 世纪9 0 年代末期，目前还没形成一个 成熟的通用数据流管理系统。随着互联网技术的发展和广泛应用，国际、国内对数据 流的研究已逐步得到重视，国际上现在有多个著名的科研机构j 下在进行数据流处理的 研究，按照研究数据流处理的动机，这些研究项目小组大致可以分为两类。第一类以 s t a n f o r d 大学的s t r e a m 项目小组为代表，他们在此以前是研究关系数据库的，因此 第2 页 第一章引言 试图借鉴关系数据库的方法，将关系数据模型、查询语言等关系数据库中的概念推广 到数据流模型下，以建立一个通用的数据流管理系统【l 】。另一类以b r o w n 大学的a u r o r a 项目小组为代表，他们从某个具体应用出发，构造适合于某类具体应用的数据流处理 系统【2 1 。 1 2 1 几个重要的概念 l 、数据流( d a t a s t r e a m ) 数据流的定义存在多种说法，如【3 】定义数据流为从源到目的持续流动的数据；【4 】 定义数据流为一个有序的、只读一次或很少次数的数据序列。在此，我们使用 2 9 】中的 定义，即数据流被定义为数据元素的有序序列，序列中的数据元素顺序到达数据流处 理系统。 数据流处理系统的输入数据是以一种瞬间的、连续的、动态的流的形式到达。总 的来说，相对于传统数据库管理系统，数据流处理系统主要有如下几个方面的特征： ( 1 ) 输入数据是动态到达的，从理论上来说，它的大小是无边界的； ( 2 ) 系统中的数据是动态的，而对数据的查询是相对静止的； ( 3 ) 一旦数据流中的某个元素经过处理，要么被丢弃，要么被归档存储，因此 要访问已经流过的数据，要么是不可能的，要么代价很高l 2 9 1 。 2 、滑动窗口( s l i d e w i n d o w ) 在数据流的查询中，用户往往需要限定查询所涉及到的数据范围，被限定的数据 范围被称为窗口。滑动窗口的定义也存在多种形式，如【3 0 】根据查询的开始时间和结束 时间是否变化等特点把窗口分为快照窗口( s n a p s h o tw i n d o w ) 、界标窗1 ：3 ( l a n d m a r k w i n d o w ) 和滑动窗口( s l i d i n gw i n d o w ) ，其中，当查询的开始时间和结束时间都变化 时，此时窗口被称为滑动窗口。 若时间被分成等长的、离散的时间步( t i m es t e p ) ，并以时间步为逻辑单位， 5 称包含最近个时刻达到的活动元素的时间窗口为滑动窗口，为滑动窗口的大小。 相对于上述的以时间步为逻辑单位而言，若以数据元组为单位( 物理单位) ，则称 包含最近个数据元组的窗口也为滑动窗口。 在本文的研究中，我们使用滑动窗口的最后一种定义，即滑动窗口大小的度量单 位为数据元组。 3 、聚合函数( a g g r e g a t ef u n c t i o n ) 在传统数据库管理系统( d b m s ) 中，聚合函数定义为对一组值进行计算，并返 回单个值的函数。在本文的研究中，我们仍然使用该定义。常用的聚合函数有c o u n t ( 计数) 、s u m ( 求和) 、a v g ( 平均值) 、m a x ( 最大值) 、m i n ( 最小值) 。在本文 中，我们还引入了除上述5 个常用聚合函数之外的函数，它们是s t d e v ( 基于样本 第3 页 摹于数据流的聚台函数精确计算研究及其应用 郑耀东 个体的标准偏差) 、s t d e p ( 基于样本总体的标准偏差) 、v a r ( 基于样本个体的方差) 和v a r p ( 基于样本总体的方差) 。 l - 2 2目前流行的数据流管理系统 最近几年，数据流处理技术发展很快，一方面，出现了很多流数据模型下的管理 系统，即数据流管理系统( d a t as t r e a mm a n a g e m e n ts y s t e m ，简称d s m s ) 主要包括 s t a n f o r d 大学的s t r e a m 项目 1 1 、加州大学伯克力分校的t e l e g r a p h c q 项目】、 b r a n d e i s 大学、b r o w n 大学和m i t 合作研究开发a u r o r a 工程等。这些系统针对具体 行业背景，给出比较全面的数据流管理的解决方案。下面将详细介绍这几个数据流管 理系统。 l 、s t r e a m 系统 s t r e a m ( s t a n f o r ds t r e a md a t am a n a g e r ) 系统由s t a n f o r d 大学计算机系创建的一 个数据流管理系统研究项目，由著名关系数据库专家r a j e e vm o t v a n i 教授和j e n n i f e r w i d o m 教授领导，并由美国国家自然科学基金( n s f ) 提供支持。它主要对复杂的、 持续的、快速的、多变的数据流进行处理。它的主要目标是研究一个通用的数据流管 理系统，包括提供一个通用的，灵活的体系结构；相关的理论结果和算法，数据模型， 相关的语言和语义：探讨多个连续的，快速的，时问可变的数据流的连续查询处理， 优化，和资源分配问题。希望最后提供全面，通用的数据流管理系统，用户可以用类 似于s q l 申明型语言来指定查询，监控。目前他们在数据流管理系统的体系结构，数 据模型和语义，语言，资源分配和查询优化，数据流的统计取得了部分结果。如 s t r e a m 系统讨论了数据流系统的模型i l j ，并定义数据流查询语言c q l ( c o n t i n u o u s q u e r yl a n g u a g e ) 例的具体语义。 2 、t e l e g r a p h c q - r - 程 t e l e g r a p h c q 工程又称为自适应数据流查询系统，是加州大学伯克利分校于2 0 0 0 年开始的一个项目，它的目的是开发一个自适应的流数据处理体系结构，以处理数据 密集型的网络应用程序【l ，包括自适应连接和自适应操作符顺序调整等，其中研究的 数据流主要来自传感器、日志、p e e r - t o - p e e r 等系统。它由美国国家自然基金和c a l i f o m i a m i c i 的计划支持，由m i k ef r a n k l i n 和j o eh e l l e r s t e i n 负责。 3 、a u r o r a - z - 程 a u r o r a 工程由b r a n d e i s 大学、b r o w n 大学和m i t 合作研究开发，它是专门针对 流监控应用开发一个新的数据处理系统，主要实现对传感器数据、各种嵌入式设备的 数据进行实时监控和查询等功能【2 】。a u r o r a 工程目前支持下面三种类型的应用： 1 ) 实时监控应用，该应用可以不断地监控事物的状态，并且对从环境获取的当 第4 页 第一章引言 前到达数据感兴趣，在这些应用中，一般不需要和只需要存储少量数据。 2 ) 档案应用，该应用是过去一个很典型的应用，它主要需要按照时间序列处理 大量存储的数据。 3 ) 生成子图应用，该应用需要知道事物的过去状态和当前状态，需要对当前数 据和存储的历史数据进行比较。 1 3 问题定义 在本文中，基于数据流滑动窗口模型的计算聚合函数的装置原理图如图1 - 1 所示， 该装置包括数据输入模块、数据输出模块、计算模块、保存和更新历史数据模块。计 算聚合函数的值的时刻是当数据进入滑动窗口时、或者数据从滑动窗口中被删除时的 两个时刻。 赦捌辅入 数械带戢| i i 譬扮燃擞蜊 彀挺遵 澍渤辫j 对 扮i 十嚣 计摔蜒襞 汁嚣模块 掰电教擀存站嚣 艇暂埘熏数据 觳蛾鞠“ 彀粥从，乎岫前i i 内j i 宣 蚪障时嗨许嚣 图1 - 1计算聚合函数的装置原理圈 在传统数据库管理系统( d b m s ) 中，聚合函数定义为对一组值进行计算，并返 回单个值的函数。在本文的研究中，我们仍然使用该定义。常用的聚合函数有c o u n t ( 计数) 、s u m ( 求和) 、a v g ( 平均值) 、m a x ( 最大值) 、m i n ( 最小值) 。在本文 中，我们还引入了除上述5 个常用聚合函数之外的函数，它们是s t d e v ( 基于样本 个体的标准偏差) 、s t d e p ( 基于样本总体的标准偏差) 、v a r ( 基于样本个体的方差) 和v a r p ( 基于样本总体的方差) 。为了后续的说明方便性，在此把上述提及的聚合函 数分成下面三类： ( 1 ) s u m 、a v g 、s t d e v 、s t d e p 、，a r 、a v r p ： ( 2 ) ( 、m i n ： ( 3 ) c o u n t 。 其中，第( 1 ) 和( 2 ) 类型的聚合函数只能用于输入数据为数值类型的计算，第 ( 3 ) 类型的聚合函数可以用于输入数据为数值类型或者字符串类型的计算，但在本 文中只考虑输入数据为字符串类型的计算。 第5 页 基于数据流的聚台函数精确计算研究及其应用郑耀东 1 4 内容安排 本文的第二章介绍了聚合函数的近似计算和精确计算的常用计算方法，以及后缀 树相关理论和字符串频率统计等研究现状。第三章介绍了一种基于数据流滑动霸i z i 聚 合函数的m a x 函数和m i n 函数的精确计算方法，并给出了计算方法的理论分析与证 明，并对实验结果进行分析。第四章介绍了利用字符串频率统计方法实现的基于后缀 树的骨干网络垃圾邮件检测方法，并对实验结果进行分析和比较。第五章对全文进行 总结，同时展望下一步工作。 第6 页 第二章研究现状 第二章研究现状 本章主要介绍聚合函数的计算方法，以及本文在计算聚合函数值时需要的相关研 究等内容。根据计算结果是否精确这一个特点，可以把聚合函数的计算可以分为近似 计算和精确计算。近似计算是计算聚合函数的近似值，即计算结果和精确结果相比较， 可能存在一定的误差，是一个近似值。精确计算是计算聚合函数的精确值。 2 1 聚合函数的近似计算 数据流模型根据不同的时序范围可以划分成多种子模型，包括界标模型( 1 a n d m a r k m o d e l ) 、滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 和快照模型( s n a p s h o tm o d e l ) 。基于 界标模型的近似计算方法比较多，如等宽直方图方法、普通抽样方法、h a s h 方法等。 基于滑动窗口模型的近似计算方法也比较多，如基本窗口方法( b a s ew i n d o w ) 、指数 直方图方法( e x p o n e n t i a lh i s t o g r a m ) 、链式采样方法等下面主要介绍基于滑动窗口模 型的近似计算方法。 2 1 1 基本窗口方法 如果按照时间序列将窗口划分为大小相等的子窗口，称之为基本窗口方法i “】，如 图2 1 所示。设窗口大小为w ，子窗口的个数为k ，则每个子窗1 ：3 包含纬么个元素， 且每个子窗口存在一个“小结构”表示该子窗口的特征。 如果某个子窗口内所包含的所有元素都已经过期，则删除该窗口，同时表示该子 窗口特征的“小结构”也被删除。聚合函数的近似计算在未过期的子窗口的“小结构” 上进行。 s l i & 姆 f f m & m - 口丁工口口 工口口丁工口口 工口 辫 麓r 潞妇 d i 鼬目搿黜目洳5 “目 图2 - 1 滑动窗口和基本窗口之间的关系图 设数据存储在滑动窗口s t 一、：叶1 t 】中，并设w = k b ，其中b 基本窗1 ：3 的长度，k 表 示基本窗口的数量，并使用序列s 【0 】，s 1 】，s l k - l 】表示基本窗口序列，其中s 【i 】_ s 【( t w ) + i b + 1 ( t - w ) + ( i + 1 ) b 】。则s 【k 】表示新的基本窗口，s 【0 】表示过期的基本窗口。 基本窗口方法中最关键点是如何确定基本窗口的大小，它必须满足任意时刻的滑 第7 页 基于数据流的聚合函数精确计算研究及其心用郑耀东 动窗口的划分，这的确是一个两难性问题。 2 1 ，2 指数直方图方法 在滑动窗口计算模型中，指数直方图方法是一个很重要方法，它最早用来生成基 于滑动窗口模型的概要数据结构。传统的直方图方法将数据集划分成多个桶，相邻桶 的元素值连续；而指数直方图则是按照元素的到达顺序构建桶，桶的容量按照不同级 别呈指数递增，从小到大分别是1 、2 、4 、8 、1 6 、3 2 ，且各个级别桶的个数均不超 过一个预定义的阂值。每当新的元素到达时，就可能根据不同的应用需求来决定是否 创建一个最低级别的桶。 指数直方图方法能够解决滑动窗口模型下的很多问题，例如基本计数( b a s i c c o u n t i n g ) 问题、求和问题【5 】、方差问题【”1 等，文献1 4 i 提出的算法类似于指数直方图， 并具有更高的效率。 5 】使用指数直方图方法统计“l ”的个数( 聚合函数c o u n t ) ， 计算过程中更新桶的算法如下： 当有新的数据元素到达时，计算新的作废时间。如果最后的桶的时间已经作 废，则删除这个桶，并更新保存最后桶的大小的计数器l a s t 和保存所有桶 大小之和的计数器t o t a l 。 如果新到达的元素为0 ，什么都不干；否则，建立一个大小为1 的桶，并用 当前的时间设置这个桶的时间戳，将计数器t o t a l 增l 。 从右向左遍历所有的桶，看看是否有桶的个数超过【恒不等式2 】【5 】的限制。 如果有k 2 + 2 ( 其中，每个级别定义的闽值为k 2 + l ，k 为级别) 个连续的桶 具有相同的大小，那么就将其中的两个桶合并为1 个新桶，新桶的大小为被 合并的两个桶的大小之和，新桶的时间戳为被合并的桶中右边的桶的时间戳。 将大小为2 r 的桶合并可能导致大小为2 什1 的桶的数目超过k 2 + l ，因此这种 合并过程要叠代下去直到不能叠代为止。如果最左边的桶是合并的结果，那 么更新计数器l a s t 。 在上述计算过程中，每当新元素到达时，增加每个桶的时间戳，如果最后一个桶 已经作废，则删除这个桶并回收它占用的存储空间，同时更新最后一个桶的“1 ”的 个数计数器l a s t 和所有桶的“1 ”的个数的计数器t o t a l 。仅仅当新到达的元素是 “1 ”时，才创建一个大小为1 的新桶，并设置新桶的时间戳，该桶的“1 ”的个数计 数器t o t a l 加1 。因此，“1 ”的个数近似值就等于下面表达式 t o t a l l a ( 1 ) 的值。因此在计算过程中，只需要维护t o t a l 计数器和l a s t 计数器即可。 第8 页 第= 章研究现状 _ _ _ _ _ _ _ _ _ _ h _ - p _ _ 一 2 1 3 链式采样方法 采样方法也是聚合函数的近似计算一种常用方法，特别是在数据量比较大、系统 无法保存计算过程中所需要所有数据的情况下，我们首先可以使用采样方法获取数据 的概要结构，然后再计算聚合函数的近似值。采样方法分为基于序列窗口的采样方法 和基于时间戳窗口的采样方法【9 】。 相对于基于序列的窗口( 最近到达的n 个数据元素组成当前滑动窗口) 而言，主 要存在两种常用的采样算法，即基本采样方法和链式采样方法( c h a i n - s a m p l i n g ) 。其 中，基本采样方法能够维持窗口大小为n 的一个统一随机采样。但是该算法有个缺点： 它太具有周期性，若数据流中的第i 个数据元素包含在采样中，则第i + c n 个数据元素 也一定包含在采样数据中( c 为大于0 的整数) 。 链式抽样方法能够获得在滑动窗口上均匀抽样的样本集合1 9 】。假设窗口大小是w ， 则在任何时间点n ，流中的元素以概率l m i n ( n ，w ) 被添加到样本集合中去。当元素被 选择到样本集合中去时，必须同时决定一个备选元素，以便于当这个元素过期时，利 用备选元素代替该元素。由于在数据流中不能够预测将来的数据，因此，实际上仅从 【n + l n + w 】中随机选取一个数作为备选元素，当到达时间点t 时，这个备选元素才最 终被确定。备选元索以后也会过期，因此也需要为它选择一个各选元素，方法同上。 可以看出，样本集合中的任一元素，均有一个备选元素的“链”，元素过期后，马上 用“链”上的下一个元素取代它。 相对于基于时问戳的滑动窗口( 窗口的大小由元素到达的时间确定，窗口内元素 个数是可变的) 而言，常用的采样方法为优先级采样方法，它根据到达元素的优先级 进行采样。 2 _ 2 聚合函数的精确计算 聚合函数的精确计算最常用的方法是增量式计算方法。在计算开始时，首先初始 化聚合函数的值，然后，每当接收到或者删除一个数据时，采用增量式方法计算聚合 豳数的值。在计算过程中，不必等到滑动窗口内的所有数据都到达之后，再进行聚合 计算，而是在新数据到达( 或删除) 时进行聚合计算。如对于聚合函数m a x 而言， 当滑动窗口中存在两个数据的时刻，就计算该聚合函数m a x 的值，即每当滑动窗口 豹数据变化时，聚合豳数m a x 总是保存它的精确结果。除了增量式计算方法之外， 还存在其他一些精确计算方法，如在线聚合【l5 1 、在实时o l a p 系统也使用了精确计算 等方法【1 6 1 。下面将详细介绍上述所提及的计算方法。 第9 页 基十数据流的聚古函数精确计算研究及其应用郑耀东 2 2 1 基本聚合函数的计算方法 在此，基本聚合函数包括s u m 函数、a v g 函数、s t d e v 函数、s t d e p 函数、 v a r 函数和a v r p 函数。计算基本聚合函数的常用方法为增量式计算方法。设某一时 刻滑动窗口的初始数据序列为x = x 1 ，x ：，以，x 。，x 。，即共有h 个数据。之后不断 有新的数据添加到滑动窗口中和滑动窗口中旧的数据被删除，其中，设添加的数据依 次为x n 。，x ，被删除的数据依次y o x 。，x 2 ，。下面以聚合函数s u m 和聚合函 数a v g 为例介绍增量式计算方法。 1 、聚合函数s u m 1 ) 设数据进入滑动窗口之前，聚合函数s u m 的值为s u m 。，则当数据瓦进 入滑动窗口时，则可以通过下面公式 s u m 。= s u m h + z 。( 其中疗 1 ) ( 2 ) 来计算聚合函数s u m 在数据进入滑动窗口之后的值s u m 。 2 ) 设数据x 。从滑动窗口中被删除之前，聚合函数s u m 的值为s u m 。，则当数 据x ，从滑动窗口中被删除时，则可以通过下丽公式 s u m 。= s u m 。l t ，( 其中_ ，? 1 ) ( 3 ) 来计算聚合函数s u m 在数据x 。从滑动窗口中被删除之后的值s u m 。 2 、聚合函数a v g 1 ) 设数据矗进入滑动窗口之前，聚合涵数a v g 的僮为a v g , , j ，元素的个数为 c o u n t , , 一则当数据x 。进入滑动窗口时，则可以通过下面公式 a v g = 丝蒜警( 鞠 1 ) ( 4 ) 来计算聚合函数a v g 在数据“进入滑动窗1 2 1 之后的值a 阳：。 2 ) 设数据x 。从滑动窗口中被删除之前，聚合函数a v g 的值为a v g 一则当数 据x 。从滑动窗口中被删除时，则可以通过下面公式 4 v g = 丝兹筹( 鳓 1 ，c o u n t p t ) ( 5 ) 来计算聚合函数a v g 在数据矗从滑动窗口中被删除之后的值a v g 。 从聚合函数s u m 和聚合函数a v g 的增量式计算方法中可以看到，在计算过程中， 我们并不需要存储进入滑动窗口中的所有数据，丽是只需要存储在增量式计算中需要 的少数的几个值，就能够计算出任意时刻的各个聚合函数的精确值。如在聚合函数 s t d e v 、s t d e p 、v a r 、a v r p 的增量式计算中，我们只需要存储当前滑动窗1 ：3 内数 据的和s u m ( = z l + x 2 + ，+ ) 、平方和s q u a r e s u m ( = x ? + z ；+ ，+ x ；) 、 第1 0 页 第二章研究现状 玎( 滑动窗口内数据的个数) 三个值就可以计算各个聚合函数的精确值，且s u m 、 s q u a r e s u m 、n 随着数据插入滑动窗口内和从滑动窗口内删除数据而变化。 2 2 2 在线聚合 在线聚合( o r d i n ea g g r e g a t i o n ) 是一种实时计算方法，它并不同时计算所有满足 条件的数据，而是对每个数据逐个计算，在计算过程中同时显示当前计算结果、当前 计算结果和最后结果精确结果的误差，以及计算进度，并实现了在线聚合函数的 计算方法和显示在线聚合计算过程的界面( i n t e r f a c e ) ，如图2 2 所示。在线聚合也可 以同时计算多个聚合函数的值，而且还可以调节计算的速度，显示结果的界面如图2 3 所示。 图2 - 2 在线聚合中a v g 聚合函数的某一个结果显不图 图2 - 3 在线聚台a v g 聚合函数的多个结果显示图 在线聚合使用三部分共同表示计算的结果，即当前计算结果、当前计算结果和精 确结果的误差、计算进度。 当前计算结果表示当前数据的计算的精确结果。 计算进度表示在计算过程中，数据被使用的百分比。 当前计算结果和精确结果的误差表示当前计算结果和实际结果之间的误 差。 在多流应用中，也使