ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (12): 2783-2792.doi: 10.7544/issn1000-1239.2016.20160589

• 其他应用技术 • 上一篇    下一篇

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

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

  1. (广西可信软件重点实验室(桂林电子科技大学) 广西桂林 541004) (ccrsdong@guet.edu.cn)
  • 出版日期: 2016-12-01
  • 基金资助: 
    国家自然科学基金项目(U1501252,61363070,61572146,61363030);广西高等学校高水平创新团队及卓越学者计划;桂林电子科技大学创新团队资助项目

Representation and Operations Research of k\+2-MDD in Large-Scale Graph Data

Dong Rongsheng, Zhang Xinkai, Liu Huadong,Gu Tianlong   

  1. (Guangxi Key Laboratory of Trusted Software (Guilin University of Electronic Technology), Guilin, Guangxi 541004)
  • Online: 2016-12-01

摘要: 对包含亿万个顶点和边的图数据进行高效、紧凑的表示和操作是大规模图数据分析处理的基础.针对该问题提出了基于决策图的大规模图数据的一种表示方法——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树, 决策图

Abstract: Efficient and compact representation and operation of graph data which contains hundreds of millions of vertices and edges are the basis of analyzing and processing the large scale of graph data. Aiming at the problem, this paper proposes a representation of large-scale graph data based on the decision diagram, that is k\+2-MDD, providing the initialization of k\+2-MDD and the basic operation such as the edge query, inner(outer) neighbor query, finding out(in)-degree, adding(deleting) edge, etc. The representation method is optimized and improved on the basis of k\+2 tree, and after dividing the adjacency matrix of graph into k\+2, it is stored with the multi valued decision diagram, so as to achieve a more compact storage structure. According to the experimental results of a series of real Web graph and the social network graph data (cnr-2000, dewiki-2013, etc.) derived from the LAW laboratory at the University of Milan, it can be seen that the number of k\+2-MDD’ nodes is only 259%-451% of the k\+2 tree, which achieving the desired effect. According to the experimental results of random graphs, it can be seen that the k\+2-MDD structure is not only suitable for sparse graphs, but also for dense graphs. The graph data of k\+2-MDD shows that both containing the compact and query efficiency representation of k\+2 tree and realizing the efficient operation of the graph model can thus achieve the unity of description and computing power.

Key words: graph data, storage optimization, k\+2-MDD, k\+2 tree, decision diagram

中图分类号: