公开(公告)号：CN106844613A

公开(公告)日：2017-06-13

申请号：CN201710035894.1

申请日：2017-01-17

Applicant: 桂林电子科技大学

Inventor： 古天龙 ,  王荣 ,  常亮 ,  徐周波 ,  曾祥炫

IPC: G06F17/30

CPC classification number: G06F17/3028

Abstract: 本发明公开一种基于符号BDD的大规模图数据可达性索引构建方法，先根据图数据构建BDD图，即使用BDD表示有向图；再使用符号步骤来完善构建的空白索引结构列表，即填入每个节点的标识标签和区间标签。针对生成的标识标签的过程，使用符号步骤更快速的广度优先搜索出所有节点并分配标识标签。然后为每个节点生成的区间标签，根据符号步骤每个节点的可达节点都搜查出来，将这些可达节点的标识标签值的与该节点的区间标签比较，所有节点都完成该操作即形成最终区间标签。这个最终的索引结构列表即可完成静态图数据上各个节点的可达性查询任务。本发明构建的可达性索引结构列表可以完成可达性查询操作，并能够有效提高可达性索引构建速度。

公开(公告)号：CN106780640A

公开(公告)日：2017-05-31

申请号：CN201611236351.8

申请日：2016-12-28

Applicant: 桂林电子科技大学

Inventor： 常亮 ,  曾祥炫 ,  古天龙 ,  徐周波 ,  王荣

IPC: G06T9/40

CPC classification number: G06T9/40

Abstract: 本发明公开一种大规模图数据表示方法，其基于K2‑tree和聚类思想，先采用了基于密度的聚类思想将图数据抽象成邻接矩阵表示形式，再在邻接矩阵的基础上进行聚类处理，从而使包含大量值为1的元素的集群结构被包含在簇中。大量值为1的元素被包含在子矩阵中，并且将所有子矩阵对应K2‑tree的L向量进行串联成一个全局性的向量global_L，并且使用了DACs编码，这将有效降低表示邻接矩阵中每个值为1的元素所耗用的空间，即提高了存储效率。本发明能够对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩，并且提供针对图数据中节点的直接和反向邻居查询操作。