Finding Frequent Subgraphs from Graph Structured Data with Geometric Information and Its Application to Lossless Compression

摘要

In this paper, we present an effective algorithm for extracting characteristic substructures from graph structured data with geometric information, such as CAD, map data and drawing data. Moreover, as an application of our algorithm, we give a method of lossless compression for such data. First, in order to deal with graph structured data with geometric information, we give a layout graph which has the total order on all vertices. As a knowledge representation, we define a layout term graph with structured variables. Secondly, we present an algorithm for finding frequent connected subgraphs in given data. This algorithm is based on levelwise strategies like Apriori algorithm by focusing on the total order on vertices. Next, we design a method of lossless compression of graph structured data with geometric information by introducing the notion of a substitution in logic programming. In general, analyzing large graph structured data is a time consuming process. If we can reduce the number of vertices without loss of information, we can speed up such a heavy process. Finally, in order to show an effectiveness of our method, we report several experimental results.