随着计算机应用领域的丰富与扩展,图作为常用的数据结构之一,现实世界的诸多领域均用图来描述其复杂而庞大的逻辑关系,如社交网、生物信息网、智能交通网等新兴领域的建模。同时在某些复杂网络中存在多种类别的顶点,常利用标签图对此类复杂网络进行建模。如社交网中的微博,我们可以用顶点表示微博用户,任意用户之间的关注情况可通过有向边来表示,此时标签可用来表示用户的性别、所在地、关注领域等信息。子图查询作为图数据分析的关键问题,引起了研究者的广泛关注。动态标签图子图查询,即返回结构及标签值均同构于查询图的若干子图。然而子图同构查询是一个NP完全问题,随着数据图的增长且频繁更新,查询时间会大大增加,通过创建高质量的索引结构以提高查询效率已成为解决这一问题的关键。例如:微博新用户的注册、老用户的注销、用户间新增或取消关注等行为都会导致标签图的动态变化。微博应用中新用户注册、用户添加关注等行为都将抽象为标签图顶点或边的插入,微博中用户账号注销,取消关注等行为都将抽象为标签图中顶点或边的删除。对现有子图查询算法的研究发现,随着图数据规模增大且频繁更新,传统子图查询算法普遍存在查询效率低、存储开销大、忽略顶点标签信息等问题。为此,本文主要对大规模动态有向标签图的子图查询问题进行研究,本文主要内容可概括如下:(1)提出动态层次序列索引,即DHS索引。该索引利用有向无环图的偏序关系将顶点拓扑成层次序列,同时在各层序列中加入顶点编号信息,不需要提取复杂特征关系即可实现快速准确地查询。(2)针对图动态变化导致的索引变化,提出更新点拓扑扩展式索引维护策略。该策略采用增量式更新方式,仅从局部变化顶点或边进行拓扑扩展以实现对索引的动态维护,从而降低重新构建全局索引带来的巨大开销。(3)针对动态有向标签图的子图查询-SubDBGragh,提出了基于DHS索引的子图查询方法。该方法将查询图与数据图的层次序列进行逐层匹配,以过滤大量非匹配项的干扰,获得候选集,相对于图的匹配,序列匹配较为简单,可以减少同构检测的次数,从而提高查询效率。同时本文提出一种关系匹配策略用以对候选集中的边进行关系匹配以获得最终详细的查询结果图。(4)针对大规模SubDBGragh的分布式处理问题,提出分割数据集和局部层次序列索引(LDHS索引)的建立。用分割数据集存储割点及割边的信息,在进行数据处理之前把分割数据集信息加载到各分区中,在进行子图查询时分割数据集辅助相关分区完成查询操作。该方法的好处的是在查询执行时不需要同时访问多个分区的数据信息,只需要在相应的分区执行需要的查询操作,最终将查询结果连接合并成完整结果,有效的避免了查询时部分分区间数据的频繁传输。