Research on Efficient and Practical Semi-Structured Data Mining Techniques Applicable to WWW

我们开发了图挖掘技术，并对它们进行了评估和改进，如下：图不仅应用于信息学（如模式识别），而且还应用于化学和生物学等领域。在图数据库中有效地找到包含给定输入图的图是很重要的。然而，子图同构问题是NP-完全的。为了提高效率，我们研究了一种先去掉不包含输入图的图再进行处理的方法。利用这一定理，我们证明了在图的集合中，可以找出不是导出子图的图。我们提出的检索方法的图使用的数据结构的特征值和这个定理。通过与VF 2的比较等实验，对本文提出的方法进行了评价和验证。Messmer等人提出了一种有效求解子图同构B的算法 ...更多信息 基于图分解。然而，当分解生成不连通图时，计算量会大大增加。为了不减少共享子图的大小，提出了一种连接不连通图的算法。然后，我们开发了随机算法生成无标号图与n个顶点。“随机”一词的意思是从一组具有n个顶点的所有未标号图中随机均匀地选择一个图。狄克逊和Wilf给出了一种有效的算法，但他们的算法需要输入n个顶点的无标号图的个数Gn，计算困难。本文提出了一种基于狄克逊和Wilfs算法的无标号图生成算法，该算法可以消除Gn，但不能保证无标号图的完全随机生成。Gupta等人的XPush机器有一个严重的问题，即它的重构降低了它的吞吐量，因为它依赖于XML过滤器的总数。我们解决了设计一个集成的XPush机器的基础上subXPush机器，允许部分交换过滤器。我们还提出了控制访问XML数据库和XML数据挖掘的基础上的数据的统计方法。少

We developed graph mining techniques and evaluated and improved them as follows.Graph is applied to various fields like not only informatics like Pattern Recognition but also chemistry and biology, etc. It is important to find out the graphs which include the given input graph efficiently in graph databases. However, the Subgraph Isomorphism problem is known to be NP-complete. In order to increase efficiency, we investigated a method which removes the graphs not containing the input graph before proceeding it. The Interlace theorem represents relations of eigenvalues in matrix. Exploiting this theorem for graph, we showed that we can find out the graph which is not induced subgraph in graph set. We proposed the retrieving method for graphs using both a data structure based eigenvalues and this theorem. We also evaluated and validated our proposition by several experiments such as comparing it with VF2.Messmer et al. proposed the algorithm to efficiently solve the Subgraph Isomorphism b … More ased on graph decomposition. However, when unconnected graph is generated by the decomposition and the cost of computation increases very much. We proposed the algorithm to connect unconnected graphs in order not to reduce the size of shared subgraphs.For evaluating performance of a system for graph, a test data consisting of diverse graphs is needed. Then we developed random algorithms for generating unlabelled graphs with n vertices. The word "random" means that selecting a graph from a set of all unlabelled graphs with n vertices uniformly at random. Dixon and Wilf showed efficient algorithm for this purpose, but their algorithm needs Gn, the number of all unlabelled graphs with n vertices, for input and it is hard to calculate. We suggested an algorithm based on Dixon and Wilfs algorithm which can eliminate Gn but can not assure completely random generation of unlabelled graphs. We also validated our approach by comparing it with VF2.Gupta et al. 's XPush machine has a serious problem that its reconstruction degrades its throughput because it depends on the total number of XML filters. We solved to devise an integrated XPush machine based on subXPush machines to allow partial exchange of filters. We also proposed methods for controlling access to XML databases and XML data mining based on the statistics of the data. Less