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