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)
Vice Chair

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