大规模图数据的k2-MDD表示方法与操作研究

作者：董荣胜; 张新凯; 刘华东; 古天龙

来源：计算机研究与发展, 2016, 53(12): 2783-2792.

• 图数据
• 存储优化
• k2-MDD
• k2树
• 决策图

对包含亿万个顶点和边的图数据进行高效、紧凑的表示和操作是大规模图数据分析处理的基础.针对该问题提出了基于决策图的大规模图数据的一种表示方法——k2-MDD,给出了k2-MDD的构造过程以及图的边查询、外(内)邻查询、出(入)度查询、添加(删除)边等基本操作.该表示方法在k2树的基础上进行优化与改进,对图的邻接矩阵进行k2划分后,采用多值决策图进行存储,从而达到存储结构更为紧凑的目的.通过对来自米兰大学LAW实验室的一系列真实网页图和社交网络图数据的实验结果可以看出,k2-MDD结构在节点数上仅为k2树的2.59%4.51%,达到了预期效果.通过对随机图的实验结果可以看出,k2-MDD结构不仅适用于稀疏图,同样也适用于稠密图.图数据的k2-MDD表示,既具有k2树表示的紧凑型和查询的高效性,又能实现符号决策图表示下图模式的高效操作,从而实现了描述和计算能力的统一.

• 单位
  桂林电子科技大学