动态图上的可达性查询算法研究

发布时间：2020-09-21 20:36

　　 节点之间的可达性是图论研究领域中的一个基本且重要的概念,旨在回答这样一个问题:给出图上的任意两个节点u和v,是否在图上存在至少一条从节点u到节点v,的路径。获得节点之间的可达性,称为可达性查询。可达性查询在过去的数十年中,一直是计算机科学和信息技术领域的重要研究课题。最早期的研究大都基于图的传递闭包的概念,从理论角度提出了一些对可达性进行快速查询的算法。随着信息化时代的到来,基于图模型的数据信息存储方式的兴起,可达性查询在实际应用中得到了高度的关注。且随着数据信息体量的不断增长,图的规模也不断增大。因此,如何快速地获得节点之间的可达性成为了数据管理和应用中最基本的问题之一。过去的十几年中,众多研究者提出了多种高效的可达性查询算法,很大程度上解决了大规模的静态图上的可达性查询问题。但是,随着信息化时代的进一步发展,基于图模型的数据信息越来越多地呈现出动态性,反映在图上就是节点的添加与删除,以及节点之间边的插入与删除。虽然可以通过多次重用已有的静态图上的可达性查询算法来处理动态图上的可达性查询,但这并不是一种高效可行的处理方式。至此,一些研究者开始了对于动态图上可达性查询算法的研究。本文对动态图上可达性查询算法做出了深入的研究。基于一种静态图上的索引类可达性查询算法以及对有向图任意性的考虑,提出了一种适用于任意有向图,可处理边的插入和删除的动态可达性查询算法。分析了算法的时间复杂性,并通过必要的证明,保证了算法的正确性。在此前提下,将其与现有的具有相同处理能力的动态可达性查询算法进行对比实验。在模拟数据集和真实数据集上的实验结果显示,本文提出的动态可达性查询算法总体上具有可观的综合优势。
【学位单位】：华东师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：

查询效率与空间需求的权衡

有向环图Gsample

图 2.2: dual-lableing 算法实例al-labeling 算法的可达性查询基于这样 条定理：节点 u 的区间节点 v 的区间标记为 [c, d)，节点 u 可以到达节点 v 当且仅当 c

【参考文献】

相关期刊论文 前1条

1 富丽贞;孟小峰;;大规模图数据可达性索引技术:现状与展望[J];计算机研究与发展;2015年01期

本文编号：2823961