（计算机科学与技术专业论文）网络安全olap分析中数据立方体技术的研究与实现.pdf

国防科学技术大学研究生院硕士学位论文 摘要 互联网正在成为国家关键信息基础设施，事关国家和全社会的根本利益。随 着互联网技术的飞速发展，针对网络信息系统的恶意攻击正向着分布化、规模化、 复杂化、间接化等趋势发展。因此迫切需要研究新的技术以实现对大规模网络信 息系统的安全态势进行实时、准确的感知、监控和分析。如何在复杂的海量监测 数据中对当前的网络安全状态进行获取、理解，发现潜在的变化趋势，从而把握 大规模网络的宏观安全态势，是我们研究工作的出发点。 联机分析处理( o l a p ) 技术是实现对大规模网络监测数据进行近实时综合分析 的重要手段。o l a p 通过对信息的多种可能的观察形式进行快速、稳定一致和交互 性的存取，允许管理决策人员对数据进行深入观察，具有极大的分析灵活性。 数据立方体的有效计算是支撑o l a p 分析的关键。只有预先计算数据立方体 的全部或部分，才能大幅度降低查询响应时间，提供联机分析处理的性能。如何 在存储容量、计算能力的限制下，寻找到计算部分数据立方体的可伸缩的办法， 在数据立方体的时空开销和查询响应性能之间进行微妙的折中，是本文工作的核 心问题。 基于网络安全态势的感知、监控和分析对实时性的需求，本文研究了数据流 上的联机分析处理。数据流上数据立方体的计算其时空条件更加苛刻，研究有限 时空条件下数据流立方体的部分物化方法，是本文工作的重点。 本文的主要工作概述如下： 1 介绍了数据立方体的基本概念和模型定义，讨论了数据立方体的实现方案， 对各种数据立方体计算算法做了总结和深入分析。 2 分析了数据流上的联机分析处理的特点，总结了数据流立方体的设计需求， 提出了多层次倾斜窗口模型，在有限的时空条件下通过时间维有效的压缩了数据 流立方体的体积。 3 提出了一种新的数据流立方体部分物化方法一基于d w a r f 结构的多维数据 流立方体框架s t r e a m d w a r f ，并给出相应的计算算法，包括增量更新算法和查询算 法，并对算法进行实现，给出实验测试结果。 4 研究开发了基于s t a r o l a p 平台的网络安全态势分析系统，实现了对海量 网络安全监测数据的多维多层次、近实时的综合分析。 关键词：数据立方体，0 l a p ，数据流立方体，s t r e a m d w a r f ，网络安全态势 惑知 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t i n t e m e th a sb e c o m et h ek e yi n f o r m a t i o nf a c i l i t yo fo u rc o u n t r y w i t ht h er a p i d d e v e l o p m e n to fi n t e r n e tt e c h n o l o g y , v i c i o u sa t t a c k sa g a i n s tn e t w o r ki n f o r m a t i o ns y s t e m t e n dt ob ed i s t r i b u t e d , c o m p l i c a t e d ，i n d i r e c ta n ds c a l a b l e t h u si t si m p e n d i n g l y r e q u i r e d t or e s e a r c hf o rn e w t e c h n o l o g yt oa c c u r a t e l ya c q u i r e ，m o n i t o ra n da n a l y z et h es e c u r i t y s i t u a t i o no fl a r g es c a l en e t w o r ks y s t e mi nr e a lt i m e f i g u r i n go u tm e t h o d st oa c q u i r ea n d i n t e r p r e tc u r r e n ts e c u r i t ys t a t eo ft h en e t w o r ka n dd i s c l o s et h eu n d e r l y i n gc h a n g e st o g r a s pt h eg e n e r a ls e c u r i t ys i t u a t i o ni sw h e r eo u rs t u d yb e g i n s o n l i n ea n a l y t i c a lp r o c e s s i n g ( o l a p ) i sa ni m p o r t a n tt e c h n o l o g yt od oi n t e g r a t e d a n a l y s i so nt h em a s s i v ea n dc o m p l i c a t e dn e t w o r km o n i t o r i n gd a t a b yr a p i d ，c o n s i s t e n t a n di n t e r a c t i v ea c c e s so fi n f o r m a t i o nf r o mv a r i o u sp o s s i b l ev i e w p o i n t s ，o l a pa l l o w s t h ea n a l y s t st oo b s e r v ed a t ai nd e p t h ，p r o v i d i n gg r e a t ef l e x i b i l i t y e f f i c i e n tc o m p u t a t i o no fd a t ac u b ei st h ek e yt os u p p o r to l a pa n a l y s i s t og e t o l a p c a p a b i l i t y , w eh a v et op r e c o m p u t et h ew h o l eo ra tl e a s tp a r t i a ld a t ac u b ei no r d e r t or e d u c et h eq u e r yr e s p o n s et i m e t h ec o r ep r o b l e mo fo u rs t u d yi st of i n do u ts c a l a b l e t e c h n i q u e s t oc o m p u t ep a r t i a ld a t ac u b eu n d e rr e s t r a i n t so fs t o r a g es p a c ea n d c o m p u t a t i o np o w e rt og e tab a l a n c eb e t w e e nd a t ac u b e sc o m p u t a t i o n & s t o r a g ec o s ta n d q u e r yr e s p o n s et i m e s i n c et h ea c q u i r e m e n t ，m o n i t o r i n ga n da n a l y s i so fn e t w o r ks e c u r i t ys i t u a t i o ni s o f t e nr e q u i r e dt ob ed o n ei nr e a lt i m e ，w ep r o c e e dt ot h es t u d yo fo n l i n ea n a l y t i c a l p r o c e s s i n go nr a p i dc h a n g i n gs t r e a m s w i t hs t r e a m s ，t h ed a t ac u b ec o m p u t a t i o nh a sa m o r er i g o r o u sr e s t r i c to nc o m p u t a t i o nt i m ea n ds t o r a g es p a c e s t u d y i n gp a r t i a l m a t e r i a l i z a t i o nt e c h n i q u e so fs t r e a mc u b eu n d e rr e s t r a i n t si st h ee m p h a s e so fo u rw o r k w es u m m a r i z eo u rw o r ka sf o l l o w f i r s t b a s i c c o n c e p t so fd a t a c u b ea r ei n t r o d u c e dw i t hd i s c u s s i o no fi t s i m p l e m e n t a t i o ns c h e m e sf o l l o w e d s e c o n d ，t h ec h a r a c t e r i s t i c so fo n l i n ea n a l i t i c a lp r o c e s s i n go nd a t as t r e a m s ，a n d t h ed e s i g nr e q u i r e m e n t so fs t r e a mc u b ea r ea n a l y z e d t h e nah i e r a r c h i c a lt i l t e dw i n d o w m o d e l ，w h i c hd e c r e a s e st h es i z eo fs t r e a mc u b et oa d a p tt ot h ec o m p u t a t i o na n ds t o r a g e c o n s t r a i n t s ，i sp r o p o s e d t h i r d ，an e wm e t h o df o rp a r t i a lm a t e r i a l i z a t i o no fs t r e a mc u b e ，ad w a r f - b a s e d s t r e a mc u b ef r a m e w o r kc a l l e ds t r e a m d w a r f , i sp r o p o s e d t h e c o r r e s p o n d i n g c o m p u t a t i o na l g o r i t h m s ，i n c l u d i n gi n c r e m e n t a lu p d a t ea l g o r i t h ma n dq u e r ya l g o r i t h m ， a r ed e v e l o p e d t h e nt h ea l g o r i t h m sa r ei m p l e m e n t e da n dt e s t i n gr e s u l t sa r ep r e s e n t e d a tl a s t ，ap r o t o t y p ef o rn e t w o r ks e c u r i t ys i t u a t i o na n a l y s i s ，w h i c hi sb a s e do n s t a r o l a pp l a t f o r ma n di sc a p a b l eo fm u l t i d i m e n s i o n a l m u l t i 1 e v e la n di n t e g r a t e d 第i i 页 国防科学技术大学研究生院硕士学位论文 a n a l y s i so nt h em a s s i v en e t w o r km o n i t o r i n gd a t ai nr e a lt i m e ，i sd e v e l o p e d k e yw o r d s ：d a t ac u b e ，o l a p , s t r e a mc u b e ，s t r e a m d w a r f ，n e t w o r k s e c u r i t ys i t u a t i o na w a r e n e s s 第i i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表2 1b u c 算法的伪代码【1 4 】1 9 表2 2 按效益选择物化视图算法的伪代码2 4 表2 3b p u s 算法的伪代码2 4 表3 1 u p d a t e s t r e a m d w a r f 算法的伪代码3 6 表3 2 u p d a t e d w a r f c u b e 算法的伪代码3 7 表3 3q u e r y d w a r f c u b e 算法的伪代码3 8 表4 1c u b e 元素定义4 6 表4 2d i m e n s i o n 元素定义4 7 表4 3j o i n 元素定义4 8 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1o l a p 体系结构2 图2 1 超市销售数据立方体1 1 图2 2 雪花模式13 图2 3 数据立方体s a l e s 计算示图1 5 图2 4 立方体格图1 6 图2 5处理树16 图2 6b u c 处理树2 0 图2 7b u c 戈0 分。2 0 图3 1时间域的多粒度划分系列3 0 图3 2 多层次倾斜窗口模型示意图31 图3 3d w a r f 子树的元组一3 4 图3 4d w a r f 子树结构3 4 图3 5 更新后的d w a r f 子树3 4 图3 6 精简后的d w a r f 子树3 5 图3 7d w a r f 子树粒度阈值的影响3 8 图3 8 数据偏斜s k e w 对d w a r f 性能的影响一3 9 图4 1s t a r o l a p 分层结构4 2 图4 2s t a r o a l p 实现框架：4 3 图4 3 历史数据多维分析5 0 图4 4 流量曲线图51 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他入已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目 学位论文作者 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目 学位论文作者 作者指导教师签名： 塾! 塾! 圣日期：沁年1 2 月l8 日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 研究背景 互联网正在成为国家关键信息基础设施，事关国家和全社会的根本利益。随 着互联网技术的飞速发展，针对网络信息系统的恶意攻击正向着分布化、规模化、 复杂化、间接化等趋势发展。据估计，目前大约有5 8 ，0 0 0 多种已知病毒，它们的 存在严重地威胁着网络信息系统的安全。著名的红色代码蠕虫病毒在因特网上传 播的最初9 小时内就感染了超过2 5 万个计算机系统，造成的损失以每天2 亿美元 的速度增长，最终高达2 6 亿美元。诸如此类的蠕虫病毒以及d d o s 攻击、恶意 代码、僵尸网络和网络入侵等安全事件层出不穷，突显出了现有网络防御能力的 严重不足。因此迫切需要研究新的技术以实现对大规模网络信息系统的宏观安全 态势进行实时、准确的感知、监控和分析。 现有的网络防护设施如n e t f l o w 采集器、i d s 入侵检测系统、v d s 病毒检测 系统、v s c a n n e r 漏洞扫描器和f i r e w a l l 防火墙等为获取网络的宏观安全态势提供 了不同的数据来源，但各种来源的数据结构、内容各异，难以对其进行准确的理 解。由于大规模网络监测数据的海量性，使得数据采集一般基于抽样的方法，而 有用的数据往往淹没在大量无用的数据中，使其在采样时经常被遗漏，从而造成 了数据的不完整性。这些问题给网络安全态势的精确感知带来了挑战。如何在复 杂的海量监测数据中对当前的网络安全状态进行获取、理解，发现潜在的变化趋 势，从而把握大规模网络的宏观安全态势，是我们研究工作的出发点。 联机分析处理( o l a p ) 技术是实现对大规模网络监测数据进行近实时综合分析 的重要手段。o l a p 通过对信息( 如网络安全监测数据) 的多种可能的观察形式进行 快速、稳定一致和交互性的存取，允许管理决策人员( 如网络安全管理人员) 对 数据进行深入观察。o l a p 展现在用户面前的是一幅幅多维视图。一旦多维的数据 立方体模型建立完成，用户可以快速地从各个分析角度获取数据，也能动态的在 各个角度之间切换或者进行多角度综合分析，具有极大的分析灵活性。 o l a p 是一个复杂的系统，它从外部数据源提取数据，在多维数据库中组织多 维数据，并提供复杂的前端分析工具从多维数据库中提炼出对决策有价值的信息。 一般o l a p 系统的体系结构如图1 1 所示。 o l a p 系统的实现问题包括上述体系结构的各个方面，包括多维数据库模型的 建立，数据源的抽取、转换和加载( e t l ) ，多维数据的聚集计算等。本文关注的 是o l a p 系统实现的核心问题：数据立方体( 即多维数据集) 的计算( 也称为多 维数据的聚集、物化) 。 第1 页 国防科学技术大学研究生院硕士学位论文 9 9 9 撵纷数搦j ! 窜= 日曰 曰囿印 努籁衍忽源 ，其中： ( 1 ) d 是维的集合，d = 矗，吐，吐，以一i ，一( 面d ，0 f n 一1 ) 表示第i 个维， 其值域为d o m ( d ，1 ，值域中不同值的个数c ( d i ) 称为维的基数。 ( 2 ) m 是度量的集合，m = , n o ，m 1 ，脚2 ，州) ，n , ，( 研f m ，0 i k 一1 ) 表示第i 第1 1 页 国防科学技术大学研究生院硕士学位论文 个度量，其值域为d o m ( m i ) 。维集和度量集是不相交的，即d n m = 。 ( 3 ) e 是数据立方体中单元的集合，e = ，p 。，p ：，p p 一。 ，p = 兀：c ( z ) 。 ( 4 ) v 表示一对一的映射关系，1 ，：d m ，也就是说，在各个维上设定一个值 后，存在唯一的度量单元与之对应。 ( 5 ) a 是维的属性的集合，彳= a o ，口”，a n l ，其中a i ( t l t 彳，0 - i n - 1 ) 表示 第i 个属性的名字，其值域为d o m a ( i ) 。 ( 6 ) f 是一个一对多的映射关系，f ：d 寸a 。也就是说：每给定一个维名，存在 多个属性名与之对应，此时维名代表了一个维表。对于任何两个不同的维，它们 对应的属性集是不相交的，即v f ，f ，则f ( d j ) n f ( d ，) = 矽。 ( 7 ) h 表示多对一的映射关系，h ：a 。专a ，a i 和a j 是某个维d i 上的属性。也就 是维的属性之间存在函数依赖关系，并且相对来说，属性a i 是细粒度，属性a i 是 粗粒度。 显然，上述数据立方体的七元组定义本质上是一个多维空间中的定义。任取维 值乩，吐，以一。的组合，根据映射v 的定义，存在e 。e ，使得，v ( d o ，研，以。) = e ，； 反过来，若e ，e 是数据立方体空间中的一个单元，根据映射v 的定义，存在维值 d 。，4 ，d n l 的组合，使得e ，= v ( d 。，d l ，d n 1 ) ，这里的d i 表示维d i 的一个取值。e i 取0 或k 元组形式，0 表示在给定的维值组合上，没有产生我们感兴趣的度量数据， k 元组( x ，x 2 ，x 。) 与度量集m = m 。，m 2 ，m 对应，也就是说，如果x i 是k 元 组的第i 个成员，那么x i 是m i 在e i 下的聚合。 对应于上述的多维数据立方体模型，有一套完备的代数操作，使用户能从多个 角度，多侧面地观察数据立方体中的数据，从而深入地了解包含在数据中的信息。 下面我们描述施加给数据立方体的三个主要的代数操作： ( 1 ) 切片( s l i c e ) 在数据立方体中选定两个维，固定其它维的取值，在选定的两个维上各取一个 区间，这就是数据立方体的切片。切片的结果是一个二维的“平面。 ( 2 ) 切块( d i c e ) 在数据立方体中选定三个维，固定其它维的取值，在选定的三个维上各取某一 个区间，这就是数据立方体的切块。切片的结果是一个三维的“空间”。从另一 个角度来讲，切块可以看成是在切片的基础上，进一步确定某一个维的区间得到 的片段体，即多个切片的叠合。 ( 3 ) 旋转( r o t a t e ) 数据立方体反映的是多维空间，而用户习惯于观察二维平面上的数据，因此， 第1 2 页 国防科学技术大学研究生院硕士学位论文 对于数据立方体的分析，用户只能次观察两个维。旋转即改变维的显示方向， 使用户能够观察指定的维，允许用户从多个侧面进行快速，一致和交互的数据存 取。 2 1 3数据立方体的实现方案 在逻辑上，数据立方体以多维方式组织数据，并提供一套完备的多维代数操 作，用以操作数据立方体。但物理实现上，数据立方体既可以基于多维数据库技 术，也可以建立在关系数据库技术之上。多维型数据立方体是近年来应多维分析 的要求而产生的，它以多维数据库为核心，直接支持数据的多维视图，多维数据 库在数据存储，检索以及综合上有着关系数据库不可比拟的优势。但是，多维型 数据立方体在适应维数动态变化，数据变化，大数据量和软硬件能力等方面赶不 上关系型数据立方体。关系型数据立方体以广泛应用的关系数据库技术为基础， 使用关系表存储数据立方体的数据，在技术成熟度以及各方面的适应性上较之多 维型数据立方体占有优势，是目前常用的数据立方体实现方案。 但是，关系型数据立方体也有它固有的缺点，即数据立方体提供的多维模型 和多维代数操作必须转换成相应的关系表和s q l 查询。一种折中的数据立方体实 现方案是综合上述两种数据立方体实现方案的长处，采用关系数据库存储海量的 基表数据，采用多维数据库存储聚集数据，这就是混合数据立方体。对于混合数 据立方体来说，它可以迅速从聚集中获取信息，但如果钻取到事实表，那么响应 速度比较慢。 图2 2 雪花模式 应该说，关系型结构能够较好的适应多维数据的表示和存储。关系数据库将 数据立方体的多维结构组织成两类表，一类是事实表( f a c tt a b l e ) ，用来组织度量值 以及各个维的编码值，事实表往往很大；另一类是维表( d i m e n s i o nt a b l e ) 分布在事 第1 3 页 国防科学技术大学研究生院硕士学位论文 实表的剧围，用以组织观察和分析度量信息时所使用的维信息，相对于事实表来 说，维表比较小。对于每一个维来说，有一个表用来存储该维的元数据，即维的 描述信息，包括维的层次属性以及其它属性等。事实表通过每一个维的编码值和 周围的维表联系在一起，该结构被称之为“星型模式 ，采用这样的结构能够体现 数据的多维特征，图2 2 所示的就是一个星型模式的例子。 2 2 数据立方体计算技术 快速响应查询需预计算数据立方体。本节和下一节2 3 节我们研究数据立方体 的计算技术。完整数据立方体的计算是其他改进、优化的数据立方体的基础。2 2 1 节我们考察完整数据立方体的各种计算算法，总结了其中的各种优化策略。2 2 2 节我们讨论了计算稀疏数据立方体和冰山立方体的经典算法b u c 。随着基本关系 中维数的增加和元组数的大量增长，完整数据立方体带来了巨大的时空开销，难 以适应应用的需求。减少数据立方体的体积和计算时间有两个基本途径：一是只 物化一部分最常用的视图的所有元组，这涉及到物化视图选择问题，我们在2 3 节 讨论；二是物化立方体的全部视图的部分元组，即2 2 3 节所讨论的压缩数据立方 体。 2 2 1 完整数据立方体的优化计算 2 2 1 1c u b e 算子 j i mg r a y 提出了数据立方体( c u b e ) 算子c u b eb y 7 j 用于表示一组g r o u p b y 操作，即它计算c u b eb y 子句中各属性的所有可能组合所对应的g r o u pb y 。 下面的例2 1 表示了一个数据立方体计算。 例2 1 考虑一个关系表s a l e s ( e m p l o y e e ，p r o d u c t ，c u s t o m e r ，q u a n t i t y ) ，其数据立 方体查询： s e l e c te m p l o y e e ，p r o d u c t ，c u s t o m e r , s u m ( q u a n t i t y ) a sa m o u n t f r o ms a l e s c u b eb y e m p l o y e e ，p r o d u c t ，c u s t o m e r 对c u b e b y 的属性e m p l o y e e ，p r o d u c t 和c u s t o m e r 的所有组合所对应的8 个 g r o u pb y 进行求和聚集计算，臣l j ( e m p l o y e e ，p r o d u c t ，c u s t o m e r ) 、( e m p l o y e e ， p r o d u c t ) 、( e m p l o y e e ，c u s t o m e r ) 、( p r o d u c t ，c u s t o m e r ) 、( e m p l o y e e ) 、( p r o d u c 0 、 ( c u s t o m e r ) 和a l l ( i i i g r o u pb y 属性为空的那个聚集) ，一个g r o u pb y 也被称 作一个小方体( c u b o i d ) ，这个c u b e 的计算结果如图2 3 。一般地，对于含1 1 个属 性的c u b eb y ，将要计算2 n 个不同的g r o u pb y 。 第1 4 页 国防科学技术大学研究生院硕士学位论文 s t a t e s i d e m p l o y e e p r o d u c tc u s t o m e r q u a n t i t y 1ol12 2o l 04 3io13 i d e m p l o y e e p r o d u c t ：c u s t o m e ra m o u n t la l la l la l l9 20a l la l l 6 301a l l6 4 o1l 2 5ol 04 6oa l ll2 7oa l lo 4 81a l la l l 3 910a l l3 1 01 ol3 1 11a ul3 1 2a l lla l l6 1 3a l l1l2 1 4a l llo4 i 5a l loa l l3 1 6a l l013 1 7a l la l lls 1 8 a l l a l lo 4 图2 3 数据立方体s a l e s 计算示图 2 2 1 2 立方体格 聚集函数c o u n t 、s u m 、m i n 、m a x 和a v g 是代数的，即它们具有一个关 键的特征：较详细的聚集( 即较多维上的) 可以用来计算不那么详细的聚集( 即较少 维上的) ，这个特征导致在c u b e 的所有g r o u pb y 上形成了一个格( 一种偏序关 系) 。考虑数据立方体中的两个分组g 1 和g 2 ，如果可以使用g 2 的结果来计算g l ， 那么g l 依赖于g 2 ，记为g ，g ：。例如，用g r o u pb ya ，b 的结果可以计算g r o u p b y a ，因此，( 4 ) ( a ，b ) 。偏序关系揭示了关于数据立方体中各个g r o u pb y 之间计算时的一种依赖关系。我们以立方体格( c u b el a t t i c e ) 来表示这种依赖关系。 立方体格的形式化描述是( 厶) ，l 表示元素( 即g r o u pb y ) 的集合，表示元 素依赖关系。对于立方体格( 厶) 中的任意两个元素a 和b ，口 b 表示a b ，且 a b 。元素a 的祖先，父母，儿子和子孙的定义如下： a n c e s t o r ( a ) = 6 i 口6 ) p a r e n t ( a ) = 6i 口 6 ，1 3 c ，a c ，c b ) c h i l d ( a ) = 6j b 口，1 3 c ，b c ，c = n 在这里，参数n 被称作一个划分的最小支持度( m i n i m u ms u p p o r t ) 。如果n 取1 ， 那么，冰山数据立方体就是原来的数据立方体。 第1 8 页 国防科学技术大学研究生院硕士学位论文 在b u c 算法中，输入变量i n p u t 是事实表的全部或者它的一个划分，它的每 条元组记录了各个维的取值以及相应的度量值，d i m 是聚集计算的初始维，输出是 满足最小支持度的聚集结果。 表2 1b u c 算法的伪代码【1 4 i p r o c e d u r eb o t t o m u p c u b e ( i n p u t , d i m ) g i o b a l s ： c o n s t a n ta u r ad i m s ：维的数目 c o n s t a n tc a r d i n a l i t y n u m d i m s ：每个维的基数 c o n s t a n tm i n s u p ：最小支持度 o u t p u t r e c ：输出记录 d a t a c o u n t n u m d i m s ：每个维的各个划分包含的元组数目 m e t h o d ： l ：a g g e r g a t e ( i n p u t ) ；p l a c e sr e s u l ti no u t p u t r e c 2 ：i fi n p u t c o u n t ( ) 一lt h e n o p t i m i z a t i o n w r i t e a n c e s t o r s ( i n p u t 0 ，d i m ) ；r e t u r n ； 3 ：w r i t eo u t p u t r e c ； 4 ：f o rd = d i m ；d n u m d i m s ；d + + d o 5 ：l e tc = c a r d i n a l i 够 d 】； 6 ：p a r t i t i o n ( i n p u t ，d ，c ，d a t a c o u n t d ) ； 7 ：l e t k = o ： 8 ：f o ri = 0 ；i = m i n s u pt h e n t h eb u c s t o p sh e r e 1 1 ：o u t p m r e c d i m d = i n p u t k d i m d ； 1 2 ：b o t o m u p c u b e ( i n p u t k k + c 】，( 1 + 1 ) ； 1 3 ：e n d i f 1 4 ：k + = c ： 1 5 ：e n df o r 16 ：o u t p u t r e c d i m d = a l l ； 1 7 ：e n d f o r b u c 算法的伪代码如表2 1 所示。第一步是对输入数据i n p u t 进行聚集计算( 第 l 行) ，并且输出聚集结果( 第3 行) 。对于d i m 到n u m d i m s 之间的每一个维d ( 第4 行) ，在维d 上对输入数据i n p u t 做划分( 第6 行) ，执行完划分过程后，数组d a t a c o u n t 记录了维d 的每一个不同的取值所对应的划分包含的元组数目。对于得到的每一 个划分( 第8 行) ，如果划分满足最小支持度( 对于完全数据立方计算，这总是正确 的，因为最小支持度为1 ) ，那么以这个划分作为参数递归调用b o t t o m u p c u b e 过程， 在这个划分上计算维d + l 到n u m d i m s 之间的聚集。当递归过程返回的时候，以维 d 上的下一个划分继续递归调用b o t t o m u p c u b e 过程。当处理完维d 上的所有划分 后，在下个维d + l 上重复上述的整个过程。 第1 9 页 国防科学技术大学研究生院硕士学位论文 5 怒c d 4 a b c6 a b d8 a c d1 2 b c d t 3 a b7 a c9 a d 1 l b c 1 3 b d1 5 c d 乞乏 2 a1 0 b1 4 c1 6 d 心彦 l a l l 图2 6b u c 处理树 图2 6 表示了b u c 算法的一棵处理树，数字表示了b u c 算法访问各个g r o u p b