摘要
时序图是顶点之间的连通性随时间变化的图,大规模时序图的紧凑表示和高效操作是分析和处理时序图数据的基础.提出了一种基于决策图的时序图数据紧凑表示方法——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(bucket ckd-tree)中节点数的23.17％～41.95％.实验结果验证了 kd-MDD表示时序图的优越性.
基金项目
国家自然科学基金(62062029)
国家自然科学基金(61762024)
广西自然科学基金(2017GXNSFDA198050)
维普
万方数据