基于kd-MDD的时序图紧凑表示

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