董荣胜 张新凯 刘华东 古天龙
(广西可信软件重点实验室(桂林电子科技大学) 广西桂林 541004)(ccrsdong@guet.edu.cn)
大规模图数据的k2-MDD表示方法与操作研究
董荣胜 张新凯 刘华东 古天龙
(广西可信软件重点实验室(桂林电子科技大学) 广西桂林 541004)(ccrsdong@guet.edu.cn)
对包含亿万个顶点和边的图数据进行高效、紧凑的表示和操作是大规模图数据分析处理的基础.针对该问题提出了基于决策图的大规模图数据的一种表示方法——k2-MDD,给出了k2-MDD的构造过程以及图的边查询、外(内)邻查询、出(入)度查询、添加(删除)边等基本操作.该表示方法在k2树的基础上进行优化与改进,对图的邻接矩阵进行k2划分后,采用多值决策图进行存储,从而达到存储结构更为紧凑的目的.通过对来自米兰大学LAW实验室的一系列真实网页图和社交网络图数据的实验结果可以看出,k2-MDD结构在节点数上仅为k2树的2.59%~4.51%,达到了预期效果.通过对随机图的实验结果可以看出,k2-MDD结构不仅适用于稀疏图,同样也适用于稠密图.图数据的k2-MDD表示,既具有k2树表示的紧凑型和查询的高效性,又能实现符号决策图表示下图模式的高效操作,从而实现了描述和计算能力的统一.
图数据;存储优化;k2-MDD;k2树;决策图
随着移动互联网、物联网等技术的发展,众多新应用以前所未有的方式和速度产生并积累着大量数据.在众多类型的大数据中,图数据作为一种有效描述大数据的数据结构,扮演着越来越重要的角色[1-2].由于图数据的规模日益庞大,如何对……