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

点击翻译按钮获取中文摘要

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