收稿日期：２０１３０７０２；修回日期：２０１３０８２９
作者简介：邵连龙（１９８７），男，天津人，硕士研究生，主要研究方向为数据挖掘（ａｌｏｎｇ２５０６＠１２６．ｃｏｍ）；尹沐（１９８８），男，北京人，硕士研究生，
主要研究方向为数据挖掘．
基于 ＤＢＬＰ数据的多维异质网络
ＧｒａｐｈＯＬＡＰ设计与实现
邵连龙，尹 沐
（北京邮电大学 北京市智能通信软件与多媒体重点实验室，北京 １００８７６）
摘 要：为了分析 ＤＢＬＰ数据中的多种类型的实体信息，挖掘其中特定的知识，首先根据异质网络 ＧｒａｐｈＯＬＡＰ
（图联机分析处理）模型，建立相应的数据仓库模型；然后依据实体维的概念，构建多维异质图立方模型；最后针
对 ＧｒａｐｈＯＬＡＰ处理异质网络能力不足的问题，补充了旋转和拉伸操作，并完善了 ＧｒａｐｈＯＬＡＰ原型系统 Ｌｉｔｅｒ
Ｍｉｎｅｒ。实证表明设计的原型系统可以有效地对 ＤＢＬＰ数据中的多维异质网络进行分析，挖掘出研究人员需要的
知识。
关键词：图挖掘；图联机分析处理；数据仓库；图立方体
中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１００１３６９５（２０１４）０３０７２００５
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１４．０３．０１９
ＨｅｔｅｒｏｇｅｎｅｏｕｓｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＧｒａｐｈＯＬＡＰｄｅｓｉｇｎａｎｄ
ｉｍｐｌｅｍｅｎｔａｔｉｏｎｂａｓｅｄｏｎＤＢＬＰ
ＳＨＡＯＬｉａｎｌｏｎｇ，ＹＩＮＭｕ
（ＢｅｉｊｉｎｇＫｅｙＬａｂｏｒａｔｏｒｙｏｆＩｎｔｅｌｌｉｇｅｎｔＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓＳｏｆｔｗａｒｅ＆ Ｍｕｌｔｉｍｅｄｉａ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓ＆ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｂｅｉｊｉｎｇ
１００８７６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｗｈｅｎｗｅｗａｎｔｔｏａｎａｌｙｚｅｔｈｅｅｎｔｉｔｙｉｎｆｏｒｍａｔｉｏｎａｎｄｍｉｎｅｔｈｅｎｅｃｅｓｓａｒｙｋｎｏｗｌｅｄｇｅ，ａｃｃｏｒｄｉｎｇｔｏｔｈｅｈｅｔｅｒｏｇｅｎｅｏｕｓ
ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＧｒａｐｈＯＬＡＰ（ｇｒａｐｈｏｎｌｉｎｅａｎａｌｙｔｉｃａｌｐｒｏｃｅｓｓｉｎｇ）ｆｒａｍｅｗｏｒｋ，ｆｉｒｓｔｌｙｔｈｉｓｐａｐｅｒｍｏｄｅｌｅｄｔｈｅｈｅｔｅｒｏｇｅｎｅｏｕｓ
ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＧｒａｐｈＯＬＡＰｄａｔａｗａｒｅｈｏｕｓｅ
，ｔｈｅｎｍｏｄｅｌｅｄｔｈｅｈｅｔｅｒｏｇｅｎｅｏｕｓｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌｇｒａｐｈｃｕｂｅｔｏａｄａｐｔｔｏｅｎ
ｔｉｔｙｄｉｍｅｎｓｉｏｎａｌａｎａｌｙｓｉｓ．ＦｉｎａｌｌｙｉｔａｄｄｅｄｒｏｔａｔｅａｎｄｓｔｒｅｔｃｈｏｐｅｒａｔｉｏｎｓｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆＧｒａｐｈＯＬＡＰ’ｓｐｏｏｒａｂｉｌｉｔｙｔｏ
ｗａｒｄｓｈｅｔｅｒｏｇｅｎｅｏｕｓｎｅｔｗｏｒｋ，ａｎｄｉｍｐｌｅｍｅｎｔｅｄｈｅｔｅｒｏｇｅｎｅｏｕｓｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＧｒａｐｈＯＬＡＰｐｒｏｔｏｔｙｐｅ，ＬｉｔｅｒＭｉｎｅｒ．Ｉｔｉｓ
ｐｒｏｖｅｓｅｆｆｅｃｔｉｖｅｏｎａｎａｌｙｚｉｎｇｈｅｔｅｒｏｇｅｎｅｏｕｓｎｅｔｗｏｒｋｓｉｎＤＢＬＰｄａｔａａｎｄｍｉｎｉｎｇｔｈｅｋｎｏｗｌｅｄｇｅｔｈａｔｉｓｎｅｅｄｅｄｂｙｒｅｓｅａｒｃｈｅｒｓ．
Ｋｅｙｗｏｒｄｓ：ｇｒａｐｈｍｉｎｉｎｇ；ＯＬＡＰ；ｄａｔａｗａｒｅｈｏｕｓｅ；ｇｒａｐｈｃｕｂｅ
!
引言
１９９３年关系数据库之父 Ｃｏｄｄ提出联机分析处理（ＯＬＡＰ）
的概念，它成为继联机事务处理（ＯＬＴＰ）之后，数据处理及相关
数据库领域的热门问题。十多年来从理论研究到实用工具、产
品及商业应用取得很大发展，
ＯＬＡＰ已经逐渐成为一项成熟的
技术。
随着对于 ＯＬＡＰ技术的深入研究，可以看到传统的 ＯＬＡＰ
技术无法支持带有图结构的网络分析。直到 ２００７年，吴巍
［１］
提出了 ＬｉｎｋＯＬＡＰ的概念，通过将面向实体的分析扩展为面向
连接的分析，他发现 ＬｉｎｋＯＬＡＰ操作在某些特定的分析场景下
能提供比传统 ＯＬＡＰ更优秀的解决方案。他以复杂网络可视
化为基础，将 ＯＬＡＰ技术应用到面向连接的分析，突破了以往
传统 ＯＬＡＰ系统中单调的二维表格表现方式。同年，Ｃｈｅｎ等
人
［２，３］
也提出了基于图结构的 ＯＬＡＰ，即 ＧｒａｐｈＯＬＡＰ的概念，
将 ＯＬＡＰ技术引入到复杂网络的分析中，解决含有多维度特性
的复杂网络的多维分析问题。他提出了 ＧｒａｐｈＯＬＡＰ特有的两
种维度，即信息维、拓扑维，并定义了两个维度上的 ＯＬＡＰ操
作，为
ＧｒａｐｈＯＬＡＰ的研究打下了理论基础，开辟了复杂网络多
维分析的一个新方向。但是最初的研究并未对 ＧｒａｐｈＯＬＡＰ的
数据仓库模型以及算法设计进行详细考虑，随后一些研究者对
这些内容进行了 补 充。２０１０年，Ｌｉ等人
［４］
提出 了 一种 适 合
ＧｒａｐｈＯＬＡＰ的数据仓库概念模型，即双星模型，并提出了信息
维聚集算法 ＩＯＬＡＰｉｎｇ和拓扑维聚集算法 ＴＯＬＡＰｉｎｇ，实现了
ＧｒａｐｈＯＬＡＰ的原型系统 ＧｒａｐｈＯＬＡＰｅｒ１．０。次年，Ｌｉ等人
［５］
又
在原有基础上提出了基于信息网络数据仓库和信息网络数据立
方体的概念，即
ＩｎｆｏＮｅｔＯＬＡＰｅｒ，提出了双星座数据模型，实现了
信息维和拓扑维的聚集算法以及上卷下钻的 ＯＬＡＰ操作，在操
作执行方面具有较高的性能。２０１１年，Ｚｈａｏ等人
［６］
详细介绍了
一个新的数据仓库模型，即基于图的数据立方体 ＧｒａｐｈＣｕｂｅ，有
效地支持针对大型多维网络进行 ＯＬＡＰ查询。同时提出了用于
ＧｒａｐｈＯＬＡＰ的新的查询方式 ｃｒｏｓｓｂｏｉｄ，这种查询方式针对多维
网络进行交叉查询，并讨论了 ＧｒａｐｈＣｕｂｅ的物化策略。２０１１
年，Ｑｕ等人
［７］
提出了一种信息网络拓扑维的框架，并基于此框
架提出了更高效的查询方法以及数据立方体的物化策略，对拓
扑维在线分析处理（ＴＯＬＡＰ）操作中特定类型度量的优化进行
第 ３１卷第 ３期
２０１４年 ３月
计 算 机 应 用 研 究
ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ
Ｖｏｌ．３１Ｎｏ．３
Ｍａｒ．２０１４
资源评论
