基于kd-MDD的时序图紧凑表示 |
| |
引用本文: | 李凤英,申会强,董荣胜.基于kd-MDD的时序图紧凑表示[J].计算机研究与发展,2022(6):1286-1296. |
| |
作者姓名: | 李凤英 申会强 董荣胜 |
| |
作者单位: | 广西可信软件重点实验室(桂林电子科技大学) |
| |
基金项目: | 国家自然科学基金项目(62062029,61762024);;广西自然科学基金项目(2017GXNSFDA198050)~~; |
| |
摘 要: | 时序图是顶点之间的连通性随时间变化的图,大规模时序图的紧凑表示和高效操作是分析和处理时序图数据的基础.提出了一种基于决策图的时序图数据紧凑表示方法——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相比,其节点数为ck...
|
关 键 词: | 时序图 紧凑表示 决策图 d-tree" kd-tree" target="_blank">name="keyword">kd-tree d-MDD" kd-MDD" target="_blank">name="keyword">kd-MDD |
|
|