一种处理图数据库中超图集合查询方法

摘要

作为一种通用的数据结构，图被广泛用来建模和表示多种复杂的结构化数据.近年来，对累积的大量图数据(即图数据库)的管理受到了研究者的广泛关注.超图集合查询是图数据库中一种具有很强现实意义的查询类型.具体地说，给定一个查询图q，超图集合查询要返回图数据库D中所有包含q的图g.提出一种新颖而有效的超图集合查询处理方法.首先，给出一种快速生成特征(feature)的方法和一种有效的树形索引结构FPTree.在FPTree的构造中，提出方法挖掘得出D中特定的频繁子图(即特征)，并合并多个频繁子图所共享的诱导子图其次，给出支持标号图的改进的ullmann算法来进行子图同构检测，一种新颖的方法可以加速子图同构检测过程.于是，基于已有的过滤和验证两步骤的查询处理框架，提出方法在过滤阶段，基于索引FPTree快速的去除一部分非结果集.由于从多个频繁子图所共享的诱导子图到查询图只进行一次子图同构检测，因此过滤时间大大减少.在验证阶段，采用改进的ullmann算法能够比现有方法更加高效的对标号图进行子图同构检测，并最终得出查询结果.最后，大量实验证实了提出方法的有效性和高效性.