Polynomial Time Matching Algorithms for Tree-Like Structured Patterns in Knowledge Discovery
Polynomial Time Matching Algorithms for Tree-Like Structured Patterns in Knowledge Discovery
复制标题
知识发现中树状结构模式的多项式时间匹配算法
DOI：
10.1007/3-540-45571-x_4
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
H. Ueda
中科院分区：
文献类型：
--
作者：
T. Miyahara;Takayoshi Shoudai;Tomoyuki Uchida;Kenichi Takahashi;H. Ueda
图具有足够的丰富性和灵活性来表达隐藏在大量数据中的离散结构。在知识发现中，利用图算法技术的一些搜索方法已经被开发出来。项图是图结构数据的一种表示形式，它是一种以超边为变量的超图。虽然术语图可以表示从结构化数据中发现的复杂模式，但在其中进行模式匹配和模式搜索是困难的。我们一直在研究术语图的子类，称为规则术语树，它适合于表达树状结构的数据。本文考虑正则项树t与标准树T的匹配问题，该问题决定是否存在树T ′，使得T ′同构于T，且T ′是用树替换t中的变量得到的.首先，我们表明，匹配问题的定期长期树和树是NP-完全的，即使每个变量在定期长期树只包含4个顶点。接下来，我们给出了一个多项式时间算法来解决规则项树和有界度树的匹配问题，使得规则项树仅具有由大于一的常数个顶点组成的变量。我们还报告了一些计算实验，并比较我们的算法与一个天真的算法。
Graphs have enough richness and flexibility to express discrete structures hidden in a large amount of data. Some searching methods utilizing graph algorithmic techniques have been developed in Knowledge Discovery. A term graph, which is one of expressions for graph-structured data, is a hypergraph whose hyperedges are regarded as variables. Although term graphs can represent complicated patterns found from structured data, it is hard to do pattern match and pattern search in them. We have been studying subclasses of term graphs, called regular term trees, which are suited for expressing tree-like structured data. In this paper, we consider a matching problem for a regular term tree t and a standard tree T, which decides whether or not there exists a tree T′ such that T′ is isomorphic to T and T′ is obtained by replacing variables in t with some trees. First we show that the matching problem for a regular term tree and a tree is NP-complete even if each variable in the regular term tree contains only 4 vertices. Next we give a polynomial time algorithm for solving the matching problem for a regular term tree and a tree of bounded degree such that the regular term tree has only variables consisting the constant number of vertices greater than one. We also report some computational experiments and compare our algorithm with a naive algorithm.