Name
Title | ||
|---|---|---|
Finding frequent subgraphs from graph structured data with geometric information and its application to lossless compression |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/3-540-36175-8_58 | PAKDD |
Keywords | Field | DocType |
layout graph,layout term graph,lossless compression,total order,frequent subgraphs,structured variable,map data,geometric information,effective algorithm,apriori algorithm,large graph,structured data,knowledge representation | Strength of a graph,Computer science,Theoretical computer science,Artificial intelligence,Geometric graph theory,Line graph,Algorithm,Directed graph,Null graph,Butterfly graph,Machine learning,Graph (abstract data type),Complement graph | Conference |
Volume | ISSN | ISBN |
2637 | 0302-9743 | 3-540-04760-3 |
Citations | PageRank | References |
1 | 0.37 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuko Itokawa | 1 | 4 | 1.14 |
| Tomoyuki Uchida | 2 | 255 | 35.06 |
| Takayoshi Shoudai | 3 | 269 | 31.89 |
| Tetsuhiro Miyahara | 4 | 267 | 32.75 |
| Yasuaki Nakamura | 5 | 105 | 140.45 |