（计算机应用技术专业论文）数据流聚集查询和频繁模式挖掘的研究.pdf

摘要 数据流模型的出现对传统的数据管理技术提出了巨大的挑战，由于数据的流动性和无限性 等特点，已有的数据库技术无法对数据流数据进行有效的管理，因此，必须进行数据流管理新 技术的研究。数据流管理技术已经引起了数据库界的广泛关注，成为当前的一个研究热点。研 究数据流相关技术不仅有重要的学术价值，而且在传感器网络、气象监测与分析、移动物体位 置跟踪、股票分析、邮件过滤、网络监控与安全等领域有着巨大的应用前景本文对数据流管 理系统和数据流挖掘中的若干关键问题进行了深入探索，主要有以下内容： ( 1 ) 数据流管理系统的体系结构：面向高速数据流，提出了一个基于硬件预处理的数据流 管理系统体系结构。目前已有的原型系统都是从查询优化、系统调度等方面来提高数据的处理 速度，在高速数据流环境下都存在明显的不足，因此，本文从一个全新的角度构建新一代数据 流管理系统，在体系结构上采用软硬件协同的思想和前端硬件预处理技术，实现数据的高速处 理。 ( 2 ) 高速数据流聚集查询：目前已有的聚集算法绝大多数是采用近似技术，以牺牲精度来 换取速度的提高。随着硬件技术的快速发展和硬件成本的迅速下降，软硬件协同技术逐渐引起 了人们的关注本文提出了一种软硬件协同的高速数据流聚集查询方法，发挥了硬件在处理速 度上的优势和软件在灵活性方面的长处，也研究了提高查询资源共享度的方法。 ( 3 ) 分布式数据流增量聚集查询：分布式处理是数据流管理系统发展的必然趋势。而在分 布式系统中，传输量往往是系统的主要瓶颈，因此，本文研究并提出了一种分布式数据流增量 聚集方法，可以显著地降低系统的通信量。 ( 4 ) 数据流频繁闭合模式：频繁闭合模式能够唯一地决定所有的频繁模式及其准确的支持 度，并且往往数量比频繁模式小几个数量级，在实际中更容易理解和应用。本文研究了动态数 据流环境下的频繁闭合模式挖掘，目前还很少有这方面的研究报道。滑动窗口和界标窗口是数 据流环境下两种最重要的窗口类型，本文分别研究并提出了基于滑动窗口和基于界标窗口的数 据流频繁闭合模式挖掘新算法，算法具有较好的适应性和可扩展性，用户可以根据需要，通过 调整允许误差在执行效率和结果精度方面取得平衡。 ( 5 ) 数据流变化检测：在数据流环境下，模式的改变往往比正常模式提供更多有价值的信 息，因此，数据流变化检测是数据流挖掘的核心问题之一。本文运用信息熵理论，从频繁项集 角度出发，提出了一种基于最大频繁项集信息熵的数据流变化检测方法，不仅可以反映关联规 则挖掘中频繁模式的变化，而且也可以有效地反映数据集的改变。 关键字：数据流；系统结构；聚集查询；软硬件协同；分布式系统；频繁闭合模式；变化检测 a b s t r a c t t h ea p p e a r a n c eo fd a t as t r e a l nm o d e l si sb r i n g i n gg r e a tc h a l l e n g e st ot r a d i t i o n a ld a t a m a n a g e m e n tt e c h n o l o g y b e c a u s eo ff e a t u r e so ff l u i d l t y a n di n f i n i t y , t h e e x i s t i n gd a t a b a s e m a n a g e m e n tt e c h n i q u e sc a nh a r d l yb ea p p l i e dt op r o c e s sd a t as t r e a m se f f e c t i v e l y t h e r e f o r e ，i t s n e c e s s a r yt os t u d yt h en e wd a t as t r e a mm a n a g e m e n tt e c h n i q u e sw h i c hh a v ea r r e s t e dal o to f d a t a b a s e r e s e a r c h e r s a t t e n t i o n d a t as t r e a mp r o c e s s i n gi sb e c o m i n gah o t s p o tr e s e a r c hi s s u e t os t u d yd a t a s t r e a m sh a sn e to n l yi m p o r t a n ts c i e n t i f i cv a l u eb u ta l s oh u g ea p p l i c a t i o no u t l o o k s ，s u c ha ss e n s o r n e t w o r k s ，w e a t h e rm o n i t o r i n ga n da n a l y s i s ，m o b i l eo b j e c tt r a c k i n g ，s t o c ka n a l y s i s ，m m lf i l t e r i n g ， n e t w o r km o m t o r i n ga n ds e c u n t y , a n ds oo n i nt i n sp a p e r , w ee x p l o r eaf e wp t i n c l p a lp r o b l e m so v f f f d a t as t r e a m sm a n a g e m e n ts y s t e ma n dd a t am i n i n g i nd e p t ht h en k c o n t e n t sa r ea sf o l l o w i n g ： ( 1 ) s y s t e ma r c h i t e c t u r eo f d a t as t r e a mm a n a g e m e n t ：f a c i n gt 0t h ed a t as t r e a m sw i t hh i g hm t e ，a n e wd a t as t r e a mm a n a g e m e n ts y s t e ma r c i n t e c t a r eb a s e de l lh a r d w a r ep r e p r o c e s s i n gi sp r o p o s e d i n e x i s t i n gd a t as t r e a mp r o t o t y p e ss y s t e m , q u e r yo p t i m i z a t i o na n ds y s t e ms c h e d u l i n ga l ea p p h e dt o i m p r o v ed a t ap r o c e s s m gr a t e ，b u tt h ei n s u f f i c i e n c yi se x i s t e dw i t ht h o s em e t h o d sw h i l emt h e e n v i r o n m e n to f l l l g hr a t ed a t as t r e a m s s o ，i nt h i s 粥t h ed a t as t r e a mm a n a g e m e n ts y s t e mo f an e w g e n e r a u o ni sc o n s t r u c t e dw i t hac o m p l e t e l yn e wa n g l e a n ds o n i ci l o v e li d e a so fh a r d w a r e s u f t w a r e c o - d e s i g na n dh a r d w a r ep r e p r o c e s s i n gt e c h n i q u e sa r ea d o p t e d ，t h u s ，t h ed a t ap r o c e s s i n gw i t hh i 曲m t e c a nb er e a l i z e d ( 2 ) a g g r e g a t i o nq u e r yo v e rh i g hr a t e d a t as t r e a l n s - b a s i c a l l y , m o s te x i s t i n ga g g r e g a t i o n a l g o r i t h m sa d o p tt h ea p p r o x i m a t i o nt e c h n o l o g yt oo b t a i nt h ea d v a n c e m e n to fr a t eb ys a c r i f i c i n gt h e a c c u r a c y w i t ht h er a p i dd e v e l o p m e n ta n dd e p r e c i a t i o no f h a r d w a r e ，t e c h n o l o g yo f h a r d w a r e - s o f t w a r e c o - d e s i g nh a sr e c e n t l yg a i n e dt h ei n c r e a s m ga t t e n t i o mi nt h i sp a p e r , w ep r o p o s eak i n do fn o v e l a g g r e g a t eq u e r ya l g o r i t h mb a s e do nh a r d w a r e - s o f t w a r ec o - d o s l g n , w h i c hi n c o q o r a t ew i t ht h e a d v a n t a g eo f b a r d w a r ei np r o c e s s i n gr a t ea n da d v a n t a g eo f s o f t w a r ei na g i l i t y ( 3 ) i n c r e m e n t a la g g r e g a t i o nq u e r yo v e rd i s t r i b u t e dd a t as t r e a m s ：d i s t r i b u t e dp r o c e s s i n gw i l lb e a ni n e v i t a b l et r e n do f t h ed e v e l o p m e n to f d a t as t r e a mm a n a g e m e n ts y s t e m , b u ti n & s t r i b u t e ds y s t e m , t r a f 右ci s u s u a l l yt h eb o t t l e n e c kr e s u u i c a o ，t h e r e f o r e ，w es t o d ya n dp r o p o s e an e wm e t h o do f i n c r e m e n t a la g g r e g a t i o nf o rd i s t r i b u t e dd a t at r a 伍c ，b yt h i sm e t h o d , t h en e t w o r kt r a f f i cc a n b er e d u c e d p r o m i n e n t l y ( 4 ) f r e q u e n tc l o s e dp a t t e r n so v e rd a t as t r e a m s ：t h es e to ff r e q u e n tc l o s e dp a t t e r n sd c t e n l l l n e s e x a c t l yt h ec o m p l e t es c to fa l lf r e q u e n tp a t t e r n sa n di su s u a l l yaf e wl e v e l ss m a l l e rt h a nt h ef r e q u e n t p a t t e r n s m o r e o v e r , f r e q u e n tc l o s e dp a t t e r n sa r em u c he a s i e rt ob eu n d e r s t o o da n dt ob ea p p h e d b u t h o wt ou l l n ef r e q u e n tc l o s e dp a t t e r n so v e rd a t as t r e a n mi sav e r yb i gc h a l l e n g ea n df e ws t u d yl q ：) o r t s o ni tc a l lb ef o u n dc u r r e n t l ys l i d i n gw m d o wa n dl a n d m a r kw i n d o wa r et w om o s ti m p o r t a n tw m c l o w s i nd a t as u e a m s i nt h i sp a p e r , t w on o v e la l g o r i t h m sw h i c hf o rm i n i n go f d a t as t r e a mf r e q u e n tp a t t e r n a n dw h i c ha r eb a s e do ns l i d i n ga n dl a n d m a r kw i n d o w sa r es u g g e s t e da n ds t u d i e dr e s p e c t i v e l y s u c h a l g o r i t h m sh a v eg o o da d a p t a b i l i t ya n de x t e n s i b i h t y f n r t h e l t l l o r e ，a c c o r d i n gt h en e e do fn s e f s ，t h e b a l a n c eb e t w e e np r e c i s i o na n de f f i c i e n c yc a l lb eo b t a i n e dt h r o u g ha d j u s t i n gp e r m i s s i b l ee r r o r ( 5 ) d e t e c t i o no fc h a n g eo v e rd a t as t r e a m s ：t h ec h a n g e so fd a t am o d e l so i t e np r o w d em o r e i n f o r m a t i o nt h a nn o r n l a ld a t am o d e l s ，c o n s e q u e n t l y , t h ed e t e c t i o no v e rd a t ac h a n g e si so n eo f t h em o s t i m p o r t a n te o r e i s s u e so fd a t as t r e a m sm m i n g i nt h i sp a p e r , w ep r e s e n tan o v e lm e t h o df o rt h e d e t e c t i o na n de s t o n a t i o no fc h a n g eb a s e do nm a x i m u mf r e q u e n ti t e m s e t sr e f o r m a t i o ne n t r o p y , t h i s m e t h o dc a nr e f l e c te f f e c t i v e l yn o to n l yt h ec h a n g e so ft h ed a t as 如e a mm o d e l so fm i n i n ga s s o c i a t e r o l e sb u ta l s ot h ec h a n g e so f d a t as e t s k e y w o r d s ：d a t as t r e a m ；s y s t e ma r c h i t e c t u r e ；a g g r e g a t i o nq u e r y ；h a r d w a r e s o f t w a r ec o - d e s i g n ； d i s m b u t e ds y s t e m ；f r e q u e n tc l o s e di t e m - s e t s ；d e t e c t i o no f e h a n g e 表1 1 d b m s 和d s m s 的比较 表3 1s t a d d s 、s z c f z 和s j z 的比较 表4 1 数据集示例 表索引 v 2 3 3 3 6 t a b l el n d e x t a b1 1c o m p a r i s o no f d b m sa n dd s m s t a b3 1c o m p a r i s o no f s a i ：d d s 、s z c f za n ds j z v i 2 3 3 3 6 图索引 图1 - 1 关系数据库管理系统模型 图1 - 2 数据流管理系统模型 图1 - 3 数据流挖掘模型 图2 1 基于硬件预处理的数据流管理系统体系结构 图2 - 2 一个滑动窗口的结构 图2 - 3 基本窗口的s u m 实现 图2 - 4 基本窗口的a v g 实现 图2 5 基本窗口的m a x 实现 图2 - 6 n s t 先进先出队列的结构 图2 7 聚集树t 的结构 图2 8 聚集树t 图2 9 s u m 仿真波形图 图2 1 0 a v g 仿真波形 图2 1 1m a x 仿真波形 图3 一l 典型内节点结构示例 图3 - 2v s b - t r e e 结构 图3 - 3 插入元组r l 和r 2 后的v s b - t r e e 结构 图3 - 4 修正后的v s b t h e 结构 图3 - 5 插入元组r 3 且修正后的v s b - t r e e 结构 图3 - 6v s b - t r e e 的节点合并 图3 - 7 分布式系统路由树 图3 - 8 系统通信量 图4 1 d s c f it r e e 结构示例 图4 - 2 d s c f it r e e 构造示例 图4 - 3 索引模式树 图4 _ 4t 1 0 1 4 d 1 0 0 0 k 的运行时间 图4 5d s c f lt r e e 的内存消耗 图4 6 三组数据集的运行时间对比 图4 - 7f p - c d s 树示例 图4 8 加入口组项集后的f p - c d s 树 图4 - 9 晟终的f p - c d s 树 图4 一l o n 段的f p - c d s 树 图4 1 1 处理c f c i n e w 后的n 1 段f p - c d s 树 图4 - 1 2 处理岛后的n ，段f p - c d s 树 图4 1 3 处理岛后的n 。段f p - c d s 树 图4 1 4 每个数据分段运行时间 图4 1 5 不同支持度阈值下的运行时间 图4 - 1 6 算法在不同数据集上的运行时间 图5 1t 1 0 1 4 d 1 0 0 0 k 的运行时间 图5 - 2t 1 0 1 4 d 1 0 0 0 k 的内存消耗 图5 - 3 三组数据集的运行时间对比 2 3 4 n!h坫侈加甜乜勉m”如弘弘卯鹅仉虮铊舵惦酊拍稻拍拍舔的的卯 f i g u r e i n d e x f i gl - 1r e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e ma r c h i t e c t u r e f i g1 - 2d a t as t r e a mm a n a g e m e n ts y s t e ma r c h i t c c n l r e f i g1 - 3m d d e lo f m i n i n g d a t as t r e a m f i g2 - 1s y s t e ma r c h i t e c t u r e0 f d s m sb a s e do nh a r d w a r e - p r e t r e a t m e n t f i g2 - 2s t r u c t u r eo f as l i d i n gw i n d o w f i 9 2 - 3i m p l e m e n t a t i o n o f s u m a g g r e g a t i o n i n a b a s e w i n d o w f i g2 - 4i m p l e m e n t a t i o no f a v ga g g r e g a t i o ni nab a s ew i n d o w f i 9 2 - 5 i m p l e m e n t a t i o n o f m a xa g g r e g a t i o n ma b a s e w i n d o w f i g2 - 6s t r u c t u r eo f i n s tf i f oq u e u e f i g2 - 7a na g g r e g a t i o n - t r e ed n i c t i l f i g2 - 8a g g r e g a t i o n - t r e et f i g2 - 9s l m u l a t o rw a v e f o r mo f s u ma g g r e g a t i o n f i g2 - l os i m u l a t o rw a v e f o n no f a v ga g g r e g a t i o n f i 9 2 - i is i m u l a t o r w a v e f o r m o f m a x a g g r e g a t i o n f i g3 - 1a ni n t e r i o rn o d es t r u c t u r e f i g3 - 2v s b - t r e es u u c t u r e f i g3 - 3v s b - t r e ea f t e ri n s e r t i n gr la n dr 2 f i g3 - 4v s b - t r e ea f t e ru p d a t e f i g3 - 5v s b - t r e ea f t e ri n s e r t i n gr 3a n du p d a t e f i g3 - 6i n c o r p o r a t ev s b 慨n o d e s f i g3 - 7r o u t i n gt r e eo f d i s t r i b u t e ds y s t e m f i g3 - 8c o m p a r i s o no f s y s t e mc o n n n u i n c a t i o n f i g4 - 1s t r u c t u r eo f t h ed s c f it r e e f i g4 2d s c f it r e ec o n s t r u c t i o n f i g4 - 3i n d e xp a t t e r nt r e e f i g4 - 4e x e c u u o nt i m eo f d a t as e tt 1 0 1 4 d 1 0 0 0 k f i g4 - 5m e m o r yu s a g eo f d s c h _ t r e e f i g4 - 6c o m p a r i s o no f e x e c u t i o nt i m eo f t h r e e & t a s e t s f i g4 7s t m c t u r eo f t h ef p - c d st r e e f i g4 - 8f p - c d st r e ea f t e ri n s e r t i n g8i t e m s e t s f i g4 - 9f i n a lf p c d s t r e e f i g4 - 1 0f p - c d st r e ei ns e g m e n tn “ f i 9 4 - 1 1f p - d s t r e e a f t e r p r o c e s s i n g c f c h l e w i ns e g m e n tn i f i 9 4 1 2 f p - d s t r e e a f t e r p r o c e s s i n g 岛i ns e g m e n tn l f i 9 4 - 1 3f p - d s t r e ea f t e r p r o c e s s i n g 岛i ns e g m e n t n l f i g4 1 4e x e c u t i o nt i m ei ne a c hs e g m e n t f i g4 - 1 5r o n t i m ew t t hd i f f e r e n tt h r e s h o l d f i g4 - 1 6r t m f i m eo nd i 伍 r e n td a t a s e t f i g5 - 1e x e c u t i o nt i m eo f d a t as e tt 1 0 1 4 d 1 0 0 0 k f i g5 - 2m e m o r yu s a g eo f d a t as e tt 1 0 1 4 d 1 0 0 0 k f i g5 - 3c o m p a r i s o no f e x e c u t i o nt i m eo f t h r e ed a t a s e t s 2 3 4 n他n：2托侈殂勉忿m”；：弭弭”强加舢甜铊铊艏钙拍铂艏撕钙钞钉卯卯 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查 阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 芬乏彤 日期：彻石7 2 , 0 第一章绪论 1 1 研究背景 第一章绪论 自2 0 世纪7 0 年代以来，数据库技术得到了迅速的发展和广泛的应用，传统数据库获得了 巨大的成功。但是，在2 0 世纪末，随着信息技术的飞速发展，一种新的应用模型却对它提出了 有力的挑战。这种称为数据流( d a t as t r e a m ) 的应用模型广泛出现在众多应用领域。例如金融市场、 网络监控、电讯数据管理、传感器网络等 i - s l 。这类数据的共同特点是不断地产生、在时间维度 上严格有序、其数值不断地变化，而且，这些数据一般都规模庞大、增长迅速。利用传统的数 据库技术管理这种数据，需要将数据全部保存在物理介质中，然后通过提交数据操级语言( d a t a m a n i p u l a t i o nl a n g u a g e ，简称d m l ) 访问物理介质来获取查询结果。但是，由于数据流数据源源 不断，在有限的存储空间中无法保存数据流的全部数据，而且，数据流应用对查询处理往往有 着很高的实时性要求，这也决定了数据不能保存下来进行处理。因此，已有的数据库技术无法 对数据流数据进行有效的管理，必须进行数据流管理新技术的研究“一 自2 0 0 0 年以来，数据流管理技术已经引起了数据库界的广泛关注。许多著名的研究机构和 大学都开始了这方面的研究，提出了一系列的理论、方法和技术，有力地推动了数据库技术的 发展。目前的研究工作主要包括两个方面：数据流管理系统和数据流挖掘算法。前者侧重于数 据流管理系统的开发和相关技术的实现，如数据流的连续查询、内存管理和系统调度等；后者 侧重于数据流的在线分析，从聚类、分类、频繁项集的挖掘以及可视化方面都做了大量的工作。 1 1 1 数据流及其特点 数据流形式的数据不同于传统的基于集合的相对静止的数据。数据流数据连续到达，频繁 变化，数据量事前是不确定的，也可能是无限的。归纳起来，数据流的共同特点是： 1 无限性。数据流是不断到来的，若要将其全部存储，需要的存储空间是无限的。 2 未知性。数据流的数据值是不断改变的，利用预测方法也不能准确地预测下一时刻将到 来的数据值。 3 不可再现性。对于数据流上的数据，一旦流过处理节点就不会再次出现。 在现实世界中，数据流应用非常广泛，例如：网络监控和交通工程、电信通信纪录、网络 安全、金融业务流、传感器网络、网络日志和网页点击流等。在数据流模型中，部分或全部数 据都以一种连续流的形式在线到达，与传统的关系模型相比，具有以下不同： 1 在数据流模型中，处理的数据不再是从磁盘和内存中随机访问读取的数据，而是一个或 多个连续的、无穷的数据项组成的时间序列。 2 数据流中的数据是实时到达的，而数据库中的数据是存储在磁盘中。 3 数据流中的数据是按序流过的，不受应用系统所控制。一般只能对数据进行顺序访问， 而磁盘中的数据可以随机访问。 4 数据流中的数据是无限的，而数据库中的数据是有限的。 5 由于在有限的储存空间内无法存储无限数据流的全部数据，因此数据流中大部分的数据 在处理后被丢弃了，除非特意保存，否则不能被再次取出处理，或者再次提取数据代价昂贵。 所以数据流上的查询多数只能得到近似的查询结果，而数据库上的查询则可以得到精确的查询 结果。 东南大学博士学位论文 6 系统只能保存数据流全部数据的一个有限子集或统计数据，并随着数据流上新数据的到 来进行更新，这种更新的频度取决于数据流数据到达的速度显然，数据流的更新频度要远远 高于数据库中数据更新的频度。 因此，在数据流应用系统中，我们不能简单地将数据流存放到传统的数据库中再进行查询。 因为传统的数据库并不是为不断快速到达的连续数据流而设计的，不能直接支持数据流应用中 典型的“连续查询”。而且，在对数据流的查询和分析中，近似性和适应性也是两个重要特点， 而传统的数据库管理系统所注重的却是通过静态的执行计划提供精确的查询结果，不支持近似 性和适应性操作。应对数据流管理的特殊要求，数据流管理系统( d s m s ) 应运而生了。 1 1 2 数据流管理系统 数据流管理系统是专门为处理数据流而设计。它的处理对象与传统的数据库管理系统 ( d b m s ) 有很大的区别，主要的区别如表1 1 所示。 表1 1 d b m s 和d s m s 的比较 比较内容 d b m sd s m s 数据关系 处理持久稳定的关系处理瞬时连续的数据流 查询方式一次性查询( o n e t i m eq u e r i e s )连续的查询( c o n t l n u o u sq u e s ) 访问方式随机存取顺序存取 存储空问极大的磁盘存储有限的内存空间 数据状态仅关注当前的状态关注历史状态和到达顺序 存储方式被动存储主动存储 数据率相对较低的更新率数据更新率高 响应时间 非实时性服务 存在实时处理的需求 精确度精确的数据非精确数据 系统特征查询计划静态生成不可预料的变化的数据特征 传统关系数据库管理系统的处理机制如图1 - 1 所示。数据存储到磁盘中，当用户提交一个 查询时，系统进行处理，然后将查询结果一次性返回给用户。而这个查询不再有效。 图1 - 1 关系数据库管理系统模型 数据流管理系统如图1 2 所示。数据在线到达之后，并不是存储到磁盘上，而是直接进入 流查询处理器，流查询处理器即时地对数据进行处理。当用户注册一个查询后，查询一直保存 有效，直到用户注销或查询到达结束时间，表现为连续查询。数据流进入查询处理器后，查询 2 第一章绪论 处理器直接根据当前注册的查询对数据进行操作，所产生的结果同样以流的形式返回给用户 为满足对历史数据查询的需要，往往也将某些数据或对数据进行压缩以数据概要的方式存储。 日 输入数据亡令 日 用户 查询u耻喇 流查询处理器 工 f 要刁 图1 - 2 数据流管理系统模型 果 目日 c 冷c j - 过期数据 日日 数据流具有着连续性和无限性的特点，数据向未来的时间方向无限延展和向过去的时间方 向无限流逝，因此，数据流系统在大多数情况下无法处理全部的数据，例如，当进行连接和聚 集操作的过程中，不可能访问到已经过期的数据和尚未到达的数据，而且当前保留的数据也受 到存储空间等诸多方面的限制。为了适应数据流的特点以及大多数实际应用的需要，在数据流 系统中广泛使用了窗口技术，连续地对数据流中的部分数据进行处理。 窗口是对数据流上数据的区域性限定，即针对数据流的无限性所作的处理，使查询对数据 流所作的操作全部限定在窗1 3 范围之内。由于窗1 3 中只包括数据流上的部分数据，查询处理得 到的不是精确的结果而是近似结果，因此，窗口技术也可以看作是一种近似查询技术。 数据流是由离散的数据单元所构成，因此，窗口的划分方式可以是基于时间也可以是基于 元组数量的，也就是说窗口的长度可以是时间单位也可以用元组数量来表示。基于时间的窗口 限定的是窗口内元组所跨越的时间长度，例如，窗口的长度为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 ) 窗口。滑动窗1 3 对窗口的起始与结束都没有明确的定义，定义的是窗口 的长度，窗口保持一定的长度在流数据上进行滑动，不断地把得到的结果输出，直至查询结束， 滑动窗口也可以定义一个结束点，当窗口前端滑动到这个点时结束查询。 窗口除了具有以上这些特性之外，还有一个重要的属性就是跳数( h o p ) ，即窗口移动的频率 特性。跳数是窗口每次需要移动的长度，因为窗口中保存的是离散的数据单元，因此窗口移动 是跳跃式的。这个跳数同样有基于时间的和基于元组的两种，分别对应于相应的窗口类型。例 如，对于一个基于时间的1 0 秒钟长度的滑动窗口，它的跳数为2 秒，则代表窗口每向前滑动2 3 东南大学博士学位论文 秒钟就需要作一次处理，基于元组数量的滑动窗口的跳数为元组的个数，其他特性与基于时间 的窗口是一样的。 1 1 3 数据流挖掘 数据流挖掘是数据流管理技术的另一个重要研究方面。数据流挖掘就是在流式数据上发现 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 一个数据流挖掘模型如图1 - 3 所示，处理的数据不再是从磁盘和内存中随机访问读取的数 据，而是一个或多个连续的、无穷的数据项组成的序列。 阳 图1 3 数据流挖掘模型 由于数据流本身的特点，许多传统的数据挖掘算法并不适合于数据流的挖掘。因为数据是 以流动的方式出现，并不象传统的数据是静态存储在磁盘中，许多数据如果没有被保存将无法 重新访问。所以，要求基于数据流的挖掘算法不能多次重复扫描数据，只能通过对数据进行一 次或少数几次扫描就完成挖掘。而且，数据流中的数据规模宏大，内存无法存储全部数据，也 使得基于数据流挖掘的算法只能利用有限的内存提取数据流的一个子集作为算法的输入数据， 所以挖掘的结果通常是近似的。由于数据不断被更新，挖掘的结果也随时间不断变化，因此， 算法应当支持增量计算，并不断将挖掘结果返回给用户。基于数据流的快速流入和数据流中的 数据量极大的特点，要求算法的时间复杂度必须较低，必须能够在内存中实现，不能进行内外 存数据交换，因为内外存数据交换会浪费大量的时间。内存资源的有限性也要求算法占用的内 存不能太大。因此，数据流的出现对传统的数据挖掘算法提出了新的挑战。 目前，数据流挖掘算法的研究主要集中在聚类、分类、频繁模式挖掘、离群点检测和数据 流的变化检测等方面。 1 2 研究现状 最近几年，国内外的数据库研究人员已经对数据流管理问题开展了大量的研究工作，涉及 到数据流管理系统及其相关实现技术和数据流挖掘等各方面的内容。 1 2 1 数据流管理系统及其相关实现技术 目前，比较典型的数据流管理原型系统有s t r e a m 、t e l e g r a p h 、a u r o r a 、n i g a r a 和c o u g a r 。 s t r e a m 是斯坦福大学数据库研究组的一个项目，其目标是实现一个通用的数据流管理系 统( d a t as t r e a m m a n a g e m e n ts y s t e m ，简称d s m s ) b 。该系统是基于关系模型提出的，其研究 内容涵盖了数据流查询处理的各个方面，如内存管理、近似查询、数据流查询语言的定义等等， 取得了很多的研究成果。在s t r e a m 系统中，查询首先被注册，随着新数据的到来，查询不停 地被执行。c q l ( c o n t i n u o u sq u e r yl a n g u a g e ) 是s t r e a m 系统的标准查询语言，它既支持传统的 4 第一章绪论 关系操作，又支持流操作。c q l - t f 展了 s q l 语言，主要表现在f r o m 子旬。f r o m 子旬包含一个可 选的滑动窗口和一个取样子句。滑动窗口由分割子句( p a r t i t i o n b y ) 、窗口大小和可选的过滤谓词 组成。分割子句把数据分为几组，在窗口内计算每组的值，然后，合并结果，类似于标准s q l 的g r a 印b y 。窗口大小f l l r o w 或r a n g e 确定，如：r a n g e1 5 m i n u t e s p r e c e d i n g 。取样子句定义了取 样的百分比，如：用s a m p l e ( 2 ) 表示取样率为2 。对于无限的数据流，s t r e a m 系统通过滑动 窗口将其转化为有限的关系元组集合。系统又定义了一些新的运算符，如i s t r e a m ( 插入流) 和 d s t r e a m ( 删除流) ，通过它们将关系元组转化为流，为用户提供连续的查询结果。s t r e a m 系 统中，每一个查询都有一个独立的查询计划。查询计划由三种不同的结构组成；查询运算符 ( q u e r yo p m t o r s ) 、操作队列( r a t e r - o p e r a t o rq u e u e s ) 、大纲( s y n o p s e s ) 。一般来说，队列是内存中用 来存储数据的一块缓冲区，有最大容量限制，因此，当数据量超出缓冲区的最大容量时，旧数 据被丢弃，以便容纳新数据。队列可以为多个运算符提供数据源。在传统的关系数据库中，两 个关系的连接操作需要多次扫描关系表，而数据流具有瞬时性，数据不停地被更新，为了实现 上述功能，s t r e a m 系统定义了大纲数据结构，用于暂时存储数据。当然，大纲不仅仅用于连 接操作。大纲与队列的重要区别是：大纲是为某种操作而服务的，容量的大小也通常根据操作 的需要而决定。有效的资源管理是数据流管理系统的关键技术之一。s t r e a m 系统中，重点关 注内存的管理，主要采用了两种技术：根据统计信息和查询注册信息，对大纲进行压缩；采用 优化的调度策略，降低队列所占用存储空间。应该指出，s t r e a m 系统还有许多不完善之处， 它是一个基于关系模型的集中式数据库系统。而对许多数据流的应用，分布式处理更为重要， 因此，s t a n f o r d 大学正计划把s t r e a m 升级为分布式系统。查询计划的形成策略还有待进一步研 究，资源分配算法还不能很好地支持近似回答，已经设计了查询语言，而且前仅仅实现了一个 子集，系统如