大规模图数据的k\+2-MDD表示方法与操作研究

来源：计算机研究与发展杂志2016年第12期北京时间：

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

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

关键词：图数据, 存储优化, k\+2-MDD, k\+2树, 决策图,