Data mining technique from huge graph structured data which are lossless compressed

随着Internet的迅速发展，许多图形结构的数据，如Web文档、电力接线图、化合物等都可以在Internet上访问。本研究的目的是提出有效的图挖掘算法，从无损压缩的图结构化数据中发现特征图模式。在此基础上，本文得出了以下研究结论：1.对于Web文档这样的树型结构数据，给出了归纳推理的多项式时间学习算法和查询学习模型的多项式时间学习算法。提出了树结构数据的树挖掘算法.为了给出图结构数据的图挖掘技术，通过对电力接线图的知识表示形式之一TTSP图模式给出多项式时间匹配算法和多项式时间最小语言问题算法，证明了TTSP图的类是归纳推理的，并给出了相应的算法。 ...更多信息 从积极的数据来看。在查询学习模型中，我们证明了TTSP图模式的有限并集是从查询中多项式时间可学习的。提出了一种从化合物数据模型外平面图中发现特征图模式的图挖掘算法.在Lempel-Zip字符串压缩算法的基础上，提出了一种适用于巨树的无损压缩算法。实验结果表明，本文提出的算法具有良好的性能。此外，基于Ferragina等人给出的树的XBW变换。在2005年，我们提出了无损压缩树的XBW变换。然后，我们提出了一个高效的搜索算法，找到一个给定的路径上的无损压缩树的XBW结构的所有出现。基于一种适用于大型无损压缩树的XBW变换，提出了一种适用于TTSP图的XBW变换。此外，我们还提出了一个有效的搜索算法，找到所有出现的TTSP图的XBW结构上的一个给定的路径。少

Due to the rapid growth of Internet, many graph structured data such as Web documents, electric power wiring diagram and chemical compounds have become accessible on Internet. The purpose of this research is to present efficient graph mining algorithms for finding characteristic graph patterns from lossless compressed graph structured data. Then, we give results of this research as follows.1. For tree structured data such as Web documents, we gave polynomial time learning algorithms on inductive inference and polynomial time learning algorithms in query learning model. Moreover, we presented tree mining algorithms for tree structured data.2. In order to give graph mining techniques for graph structured data, by giving a polynomial time matching algorithm and a polynomial time algorithm for solving the minimal language problem for TTSP graph patterns, which is one of knowledge representations of an Electric power wiring diagram, we showed that the class of TTSP graphs is inductively inf … More erable from positive data. In the query learning model, we showed that finite unions of TTSP graph patterns are polynomial time learnable from queries. Moreover, we presented a graph mining algorithm of finding characteristic graph patterns from a set of outerplanar graphs which is a data model of chemical compounds.3. Based on Lempel-Zip compression for strings, we proposed a lossless compression algorithm for huge trees. Through several experiments, we showed that the proposed algorithms have good performance. Moreover, based on XBW transformations for trees given by Ferragina, et. al. in 2005, we presented an XBW transformation of lossless compressed trees. Then, we presented an efficient search algorithm of finding all occurrences of a given path on XBW structures of lossless compressed trees.4. Based on an XBW transformation for huge lossless compressed trees, we proposed an XBW transformation for TTSP graphs. Moreover, we also presented an efficient search algorithm of finding all occurrences of a given path on XBW structures of TTSP graphs. Less