计算机研究与发展

作者：李凤英,申会强,董荣胜,

关键词：时序图, 紧凑表示, 决策图, <em>k</em>^<em>d</em>-tree, <em>k</em>^<em>d</em>-MDD,

时序图是顶点之间的连通性随时间变化的图，大规模时序图的紧凑表示和高效操作是分析和处理时序图数据的基础.提出了一种基于决策图的时序图数据紧凑表示方法——kd-MDD.kd-MDD是对kd-tree的改进，该方法对时序图的邻接矩阵进行kd划分，通过引入多值决策图来合并相同子矩阵，即kd-tree图数据表示中存在的同构子树，存储结构更加紧凑.在kd-MDD紧凑表示基础上，提供了基于kd-MDD的时序图的基本操作(如顶点正向/反向邻居的检索、边是否处于活动状态的检查、边的添加和删除等).在真实的时序图数据集上(Flickr-growth，YouTube-growth，Wikipedia等)的实验结果表明，kd-MDD表示中的节点数仅为kd-tree表示中节点数的1.58%~4.65%，与ckd-tree和bckd-tree相比，其节点数为ckd-tree中节点数的11.13%~20.39%，为bckd-tree(bucketckd-tree)中节点数的23.17%~41.95%.实验结果验证了kd-MDD表示时序图的优越性.

来源：2022年第6期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2022年第6期