Graph OLAPing的建模、设计与实现

提出了一系列Graph的OLAP模型和算法,实现了以Graph数据为中心度量的OLAP操作.主要贡献包括:(1)提出了面向Graph的数据仓库概念模型——双星模型;(2)提出了Graph的数据立方概念和创建过程;(3)设计了信息维聚集算法I-OLAPing;(4)设计了拓扑维聚集算法T-OLAPing;(5)实现了Graph OLAP的原型系统Graph OLAPer1.0.实验结果表明,设计和实现的Graph OLAPing算法及原型系统Graph OLAPer1.0能够有效地进行科研合作网分析.

基于图结构索引的分布式OLAP加速方法

随着业务数据的规模增大,一些重要的应用场景需要使用分布式在线分析处理(OLAP)支持大规模数据的分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等.同时,分布式OLAP打破单机存储的限制,可以将数据放在内存中以提升OLAP的处理性能.然而,基于内存的分布式OLAP在消除磁盘I/O后,性能瓶颈转移到了连接操作.连接操作是OLAP中的一种常用操作,会进行大量的数据读取与计算操作.通过对现有的几种连接操作方式进行分析,提出了一种能够加速连接操作的图结构索引以及基于图结构索引的连接操作方式LinkJoin.图结构索引通过用户所指定的连接关系,将数据在内存中的位置以图结构的形式进行存储.基于图结构索引的连接方式,不仅能够有等同于哈希连接的较低复杂度,而且在执行过程中能减少数据读取与计算操作次数.将目前先进的开源内存OLAP系统MonetDB从单机系统扩展成分布式系统,并且在该系统上设计与实现了基于图结构索引的连接操作方式.针对该系统的图索引结构,列式存储以及分布式执行引擎这3个重要方面,进行一系列设计与优化,以提升系统的分布式OLAP处理性能.测试结果表明,在TPC-H标准测试中,基于图结构索引的连接操作对于有连接操作的查询的平均性能提升达1.64倍(最多达4.1倍).对于这些查询中的连接操作,性能提升达9.8–22.1倍.

高效支持多维网络OLAP的数据立方体模型CI-DCG

针对现有联机分析处理(OLAP)方法的空间开销随着数据维度增加呈指数级增长,因而不适用于维度较高的多维网络应用的问题,提出了一种新的多维网络数据立方体模型——封闭冰山双立方图(CI-DCG)。该模型通过引入邻接立方体的概念,将其实例化过程转化为两个计算传统数据立方体的阶段,从而可将传统数据立方体生成算法中较为成熟的空间优化技术引入到多维网络中。在保证多维网络上OLAP查询处理效率的同时,将多维网络数据立方体生成算法的空间复杂度降为多项式级别。理论分析和实验结果均表明,该模型在空间开销和查询性能方面均优于已有的多维网络OLAP模型,并且数据维度越高,这种优势就越明显。

一种基于倒排索引的多维网络存储模型

具有多维属性的实体相互连接构成的网络(如社交网络)称为多维网络,在多维网络上支持联机分析处理具有重要的应用价值。现有方法大都从文件或数据库中逐条读取记录,当数据量很大时,需要多次读取磁盘,导致查询响应时间过长,效率较低。文中提出了一种新的基于倒排索引的多维网络存储模型II-GC(Inverted Index based Graph Cube),通过将图的拓扑结构和顶点的多维属性存储在倒排索引列表中加快查询速度,并给出了在多维网络上进行聚集查询(cuboid)和交叉查询(crossboid)的算法。在DBLP数据集上的实验表明,该模型较Graph Cube的查询效率更高,扩展性更好。

基于超图的数据结构及其在GIS中的应用

空间数据是空间分析的基础,随着海量空间数据的增大,其之间关系的日益复杂,空间数据的组织就显得愈发重要。基于超图的数据结构以超图和集合理论为基础,可以表达空间数据之间的层次关系和横向关系,使GIS空间数据结构在空间分析中的完备性和适应性问题得到解决。本论文在对超图的层次数据结构和非层次结构进行详细研究的基础上,初步探讨利用面向对象的关系数据库系统实现该模型,并以海洋数据为例,利用HBDS组织海洋原始数据、等深线数据、特征线数据、地貌数据等。论文的最后对HBDS在GIS中的应用做简单举例,并期将HBDS和OLAP相结合的方法进行数据挖掘。