Efficient Graph Sequence Mining Using Reverse Search
Efficient Graph Sequence Mining Using Reverse Search
复制标题
DOI：
10.1587/transinf.e95.d.1947
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Akihiro Inokuchi;H. Ikuta;T. Washio
中科院分区：
文献类型：
--
作者：
Akihiro Inokuchi;H. Ikuta;T. Washio
从标记图数据中挖掘频繁子图已经得到了广泛的研究。此外，近年来，从图序列中挖掘频繁模式也受到了广泛关注。一种方法，称为GTRACE，已被提出来挖掘频繁模式从图序列的假设下，图的变化是渐进的。虽然GTRACE挖掘频繁模式的效率很高，但它仍然需要大量的计算时间来挖掘包含大图和长序列的图序列中的模式。在本文中，我们提出了一个新版本的GTRACE，使有效的挖掘频繁模式的基础上的反向搜索的原则。反向搜索的基本概念是为硬枚举问题设计有效算法的一般方案。我们的性能研究表明，所提出的方法是有效的和可扩展的挖掘长和大的图序列模式，是几个数量级的速度比原来的GTRACE。
The mining of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences. A method, called GTRACE, has been proposed to mine frequent patterns from graph sequences under the assumption that changes in graphs are gradual. Although GTRACE mines the frequent patterns efficiently, it still needs substantial computation time to mine the patterns from graph sequences containing large graphs and long sequences. In this paper, we propose a new version of GTRACE that enables efficient mining of frequent patterns based on the principle of a reverse search. The underlying concept of the reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. Our performance study shows that the proposed method is efficient and scalable for mining both long and large graph sequence patterns and is several orders of magnitude faster than the original GTRACE.