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能够有效地进行科研合作网分析.

路径-维度GraphOLAP大规模多维网络并行分析框架

现实生活中,大量数据都可以使用多维网络进行建模.如何更好地对多维网络进行分析,是研究人员关注的重点.OLAP(联机分析处理)技术已被证实是对多维关系数据进行分析的有效工具,但应用OLAP技术管理与分析多维网络数据以支持有效决策,仍是一项巨大的挑战.设计并提出了一种图立方体模型:路径-维度立方体,并针对提出的立方体模型将物化过程划分为关系路径物化与关联维度物化两部分,分别提出了物化策略,并基于Spark框架设计了相关算法.在此基础上,针对网络数据设计并细化了相关的Graph OLAP(图联机分析处理)操作,丰富了框架的分析角度,提高了对多维网络的分析能力.最后,在Spark上实现了相关算法,通过对多个真实应用场景中的数据构建多维网络,在分析框架上进行了分析,实验结果表明,所提出的图立方体模型和物化算法具有一定的有效性和可扩展性.

基于DBLP数据的多维异质网络Graph OLAP设计与实现

为了分析DBLP数据中的多种类型的实体信息,挖掘其中特定的知识,首先根据异质网络Graph OLAP(图联机分析处理)模型,建立相应的数据仓库模型;然后依据实体维的概念,构建多维异质图立方模型;最后针对Graph OLAP处理异质网络能力不足的问题,补充了旋转和拉伸操作,并完善了Graph OLAP原型系统Liter Miner。实证表明设计的原型系统可以有效地对DBLP数据中的多维异质网络进行分析,挖掘出研究人员需要的知识。

断裂系统精细分析技术

断裂系统精确解释是精确构造和岩性分析的基础。概要介绍了利用地震资料断裂系统解释的多种方法的演变过程和相互联系 ,分析了它们的优缺点 ,阐述了三代相干体、倾角、方位角、方差及混沌等增强不连续的属性计算方法 ,给出了属性计算结果细线化的具体算法与应用实例。最后 。

一种具有小世界特征的结构化P2P覆盖网络

现有的P2P覆盖网络都难以把具有共同兴趣的对等点连接起来,不适用于文件浏览服务.为此,文中推广了立方连接圈(CCC)图,研究了推广立方连接圈(GCCC)图的拓扑性质,进而基于GCCC图定义了一种新的结构化P 2P覆盖网络——推广立方连接圈网络(GCNET).与其它的P2P覆盖网络相比,GCNET具有良好的小世界特征和更好的鲁棒性.模拟实验结果表明,GCNET的路由表和查询长度能达到理论下界.

几类新的笛卡尔乘积互连网络

Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络(又称圈图)、轮图等都既是Cayley图又是重要的互连网络。利用图的笛卡尔乘积方法构建了几类新的笛卡尔乘积互连网络:环网、循环移数网络、ILLIAC网络、超立方体分别与Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络、轮图的笛卡尔乘积网络;这些网络的某些性能指标(例如,直径等)比Star网络或超立方体更好。

将圈嵌入交叉立方体及其算法

图嵌入技术是研究处理器互连网络的计算性能和任务分配的重要技术，是近年来并行处理领域研究的热点之一．本文研究了交叉立方体互连网络上的圈嵌入问题，证明了任何长度为ｌ（３＜ｌ≤２ｎ）的圈均能以扩张１嵌入交叉立方体ＣＱｎ，并证明了ＣＱｎ包含２ｎ－ｋ个互不相交的长为２ｋ（１≤ｋ≤ｎ）的圈，最后给出了一个Ｏ（ｌｏｇｌ）级的圈嵌入算法．

随机图的Fibonacci数研究

简单介绍了随机图Fibonacci数的由来,给出Lucas数列和Fibonacci数列的关系,将圈图的Fibonacci数转化为Fibonacci数列.证明树的Fibonacci数的上界和下界,并给出各种常见图的Fibonacci数计算公式。

n维“格子笼”图的Hamilton问题

对n维"格子笼"图的Hamilton性进行了研究,得到了判定n维"格子笼"图是Hamilton图的一个非常简洁的充分必要条件.

超级交叉立方体互连网络上的圈嵌入

作为超立方体的变型 ,交叉立方体同时具有一些比超立方体优越的性质 ,但类似于超立方体 ,它的升级也伴随着顶点个数的增加而成倍增加 .为了解决这一问题 ,一种称为超级交叉立方体 (SCC)的互连网络被提了出来 .有关文献已证明 ,SCC很好地保持了交叉立方体在顶点度数 ,直径和连通度方面的优越性质 ,而且其升级可以增加任意多个顶点 .用图嵌入技术讨论了 SCC模拟环网络的能力 ,证明了长度为 4到 N的任一圈都能以扩张 1嵌入具有 N个顶点的 SCC,从而证明了 SCC模拟环网络的能力与交叉立方体完全相同 .

k-方体图邻点可区别全色数(英文)

本文证明 k-方体图 (k≥ 2 )的邻点可区别的全色数为 k+2 .

n维立方体的性质

n维立方体是一个n-正则的二部图,既有实际应用价值又有理论价值。文中重点研究了n维立方体的Hamilton性质及可平面性质,证明了n维立方体是Hamilton图及非平面图,并且给出了一个具体构造Hamilton圈的方法。

互连网络的新模型:多部群论模型

互连网络是超级计算机的重要组成部分。互连网络在很大程度上决定着超级计算机的性能。在1989年,S.B.Akers等提出了互连网络的群论模型,据此模型设计出了星网络、冒泡排序网络等一大批网络。尤其是星网络具有很多很好的性能,被认为是超立方体的替代品。但它们都有一个弱点:网络规模(结点数)为n!。即随着n的增大,n!增速太快,使得据此网络结构设计出的超级计算机升级较为困难,即扩展性较差。在群论模型的基础上提出了互连网络的多部群论模型,进而,据此模型设计出(n,k)-多部星网络、(n,k)-多部冒泡排序网络等多种网络。并证明星网络是(n,1)-多部星网络,而且(n,k)-多部星网络做到了规模(结点数)增大且增幅固定、直径增大缓慢、结点度不变,即有很好的可扩展性,其它(n,k)-多部网络也有类似的性能。

二维“格子笼”图的顺序偶泛圈性

给出了顺序偶泛圈图的定义,对二维"格子笼"图的顺序偶泛圈性进行了研究,得到了判定二维"格子笼"图是顺序偶泛圈图的充分必要条件。

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

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

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

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

Fibonacci立方网络上平行路径的寻径算法

目的研究在Ｆｉｂｏｎａｃｃｉ立方网络Γｎ（ｎ≥６）中寻找任意两个结点Ｓ和Ｄ之间的两条平行路径的寻径问题，并最终为实现多处理器系统中各处理器之间的信息传递提供理论依据．方法将Γｎ抽象为一个“图”进行研究．结果给出了相应的寻径算法．如果ｍ＝ｍｉｎ｛ｌ：Ｓ＜ｆｌ，Ｄ＜ｆｌ｝，则求出的两条路径满足：｜Ｐｉ（Ｓ，Ｄ）｜≤２ｍ－５，ｉ＝１，２．

盒子中蛇问题回溯算法

研究了盒子中的蛇问题 ,即求n方体Qn 中最大导出环Sn 问题 ;已知｜S2 ｜ =4,｜S3 ｜ =6 ,｜S4 ｜=8,｜S5｜=14,｜S6｜=2 6 .通过回溯算法证明了｜S7｜=48,｜S8｜≥ 94,并给出猜想 ｜Sn｜≤ 2｜Sn-1｜- 2 (n≥ 3) .该猜想对 3≤n≤ 7已成立 .

布尔路、布尔圈长度及维数

证明了ｎ － 维立方图中布尔路与布尔圈之间的内在联系，给出了布尔路。

素数立方阶群局部传递的图

目的是研究局部传递图的性质和分类.运用置换群和陪集图的理论,获得了关于素数立方阶群局部传递图的完全分类,证明了这些图是一些互不相交的关于素数立方阶群边传递图的并.