Presentation | 2003/7/24 Efficiently Mining Frequent Substructures from Large Unordered Trees Tatsuya ASI, Hiroki ARIMURA, Takeaki UNO, Shin-ichi 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 collectionof semi-structured data, where both of the patterns and the data are modeled by labeled unordered trees. The keys ofthe algorithm are efficient enumerating all unordered trees and incrementally computation of the occurrences basedon a powerful design technique known as the reverse search. We present an efficient algorithm called UNOT thatcomputes all labeled unordered trees appearing in a collection of data trees with frequency above a user-specifiedthreshold. We prove that the algorithm enumerates each frequent pattern T in O(kb2n] per pattern, where A; is thesize of T, b is the branching factor of the data tree, and n 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 # | AI2003-15 |
Date of Issue |
Conference Information | |
Committee | AI |
---|---|
Conference Date | 2003/7/24(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 | Artificial Intelligence and Knowledge-Based Processing (AI) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Efficiently Mining Frequent Substructures from Large Unordered Trees |
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 ASI |
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 | Shin-ichi NAKANO |
4th Author's Affiliation | Faculty of Engineering, Gunma University |
Date | 2003/7/24 |
Paper # | AI2003-15 |
Volume (vol) | vol.103 |
Number (no) | 243 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |