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

2016-12-22 04:19:26董荣胜张新凯刘华东古天龙
计算机研究与发展 2016年12期
关键词:结构

董荣胜 张新凯 刘华东 古天龙

(广西可信软件重点实验室(桂林电子科技大学) 广西桂林 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].由于图数据的规模日益庞大,如何对……

登录APP查看全文

猜你喜欢
结构
DNA结构的发现
《形而上学》△卷的结构和位置
哲学评论(2021年2期)2021-08-22 01:53:34
论结构
中华诗词(2019年7期)2019-11-25 01:43:04
新型平衡块结构的应用
模具制造(2019年3期)2019-06-06 02:10:54
论《日出》的结构
纵向结构
纵向结构
我国社会结构的重建
人间(2015年21期)2015-03-11 15:23:21
创新治理结构促进中小企业持续成长
现代企业(2015年9期)2015-02-28 18:56:50
半夹心结构含1,2-二硒碳硼烷的多核Co配合物的合成及结构表征