| Presentation | 2003/10/1 An Efficient Algorithm for Mining Frequent Unordered Trees from Semi-structured Data Tatsuya ASAI, Hiroki ARIMURA, Takeaki UNO, Shinichi NAKANO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we study a data mining problem of discovering frequent substructures in a large collection of semi-structured data, where both of the patterns and the data are modeled by labeled unordered trees. The keys of the algorithm are efficient enumerating all unordered trees and incrementally computation of the occurrences based on a powerful design technique known as the reverse search. We present an efficient algorithm called U NOT that computes all labeled unordered trees appearing in a collection of data trees with frequency above a user-specified threshold. We prove that the algorithm enumerates each frequent pattern T in O(kb^2m) per pattern, where k is the size of T, b is the branching factor of the data tree, and m is the total number of occurrences of T in the data trees. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | semi-structured data mining / graph mining / frequent pattern discovery / labeled unordered trees / reverse search |
| Paper # | DE2003-108,DC2003-21 |
| Date of Issue |
| Conference Information | |
| Committee | DE |
|---|---|
| Conference Date | 2003/10/1(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Data Engineering (DE) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Efficient Algorithm for Mining Frequent Unordered Trees from Semi-structured Data |
| Sub Title (in English) | |
| Keyword(1) | semi-structured data mining |
| Keyword(2) | graph mining |
| Keyword(3) | frequent pattern discovery |
| Keyword(4) | labeled unordered trees |
| Keyword(5) | reverse search |
| 1st Author's Name | Tatsuya ASAI |
| 1st Author's Affiliation | Department of Informatics, Kyushu University() |
| 2nd Author's Name | Hiroki ARIMURA |
| 2nd Author's Affiliation | Department of Informatics, Kyushu University |
| 3rd Author's Name | Takeaki UNO |
| 3rd Author's Affiliation | Natinal Institute of Informatics |
| 4th Author's Name | Shinichi NAKANO |
| 4th Author's Affiliation | Faculty of Engineering, Gunma University |
| Date | 2003/10/1 |
| Paper # | DE2003-108,DC2003-21 |
| Volume (vol) | vol.103 |
| Number (no) | 355 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |