支持动态图数据的子图查询方法

摘要：

近年来，子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的，而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题，在动态图数据上子图查询问题就变得更加困难。针对上述问题，提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引，在序列中加入标号以便数据更新后对索引进行维护，再根据序列间的匹配关系过滤出候选集合，最后采用图同构算法验证候选集中的图，最终得到结果集合。该方法的索引构造简单且体积小，并且在图数据库更新后无需重构索引，不仅支持动态图数据上的子图查询，在静态图数据上也表现出良好的性能。

关键词：子图查询、动态图数据、拓扑序列、图索引

分类号：TP311.1(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.61173031,61272178;the National Natural Science Foundation of China on International Cooperation under Grant No.61129002;the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20110042110028;the Fundamental Research Funds for the Central Universities of China under Grant Nos. N120504001, N110404015

在线出版日期：2014-02-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：139-149