论文部分内容阅读
随着大数据时代的到来，图作为表示数据之间关系的基本结构，由于其处理复杂对象之间关系的表达能力，在社交网络、软件工程、生物数据等领域有着广泛应用。查询及分析图结构数据变得越来越重要。可达性查询是检验在有向图中是否存在一个节点u到另一个节点v的路径，它是一种基础而频繁使用的查询。现实中许多问题都可以映射为可达性查询。因此，迫切需求加速查询图数据库的机制。 当前已经提出许多不同方法处理可达性查询。但是大多数方法只能在小规模图中执行，因其自身的局限性无法扩展到大规模图。此外，现有索引方法有另一个缺陷就是它们不支持图的动态更新。然而，现实应用中的图大多都是在不断变化的。针对上述问题，通过研究已有的图可达性索引算法，并分析这些算法的优缺点。本文基于区间标签方法展开了一系列的相关研究，主要研究的内容如下： （1）针对索引代价过高的问题，本文提出了一种基于双区间标签的索引方法GIDIL。该索引方法为每个节点分配一个主区间和一个辅助区间，应用这2个区间保存原图的可达性信息。其中主区间记录生成树的可达性信息，辅助区间记录非树边可达性信息。并基于GIDIL索引设计了可达性算法，有效实现图的可达性查询。 （2）为了将索引应用于动态图，支持图的动态更新操作，本文扩展了静态索引 GIDIL，提出动态可达性索引 DGIDIL。该索引方法将每个节点的区间标签进行扩展处理，在动态图上使其能够快速进行索引更新，并能有效执行可达性查询。该索引方法支持图中节点或边的插入和删除操作。 最后，本文通过大量大规模数据集上的实验证明了所提出的 GIDIL索引和DGIDIL索引方法能够在保证可达性查询性能的情况下，更快地构建可达性索引，可以扩展到大规模图，并且DGIDIL索引算法能有效地处理图的动态操作。