Efficient Substructure Discovery from Large Semi-structed Data
Tatsuya Asai, 達哉 浅井, Kenji Abe, 賢治 安部, Shinji Kawasoe, 真治 川副, Hiroki Arimura, 博紀 有村, Hiroshi Sakamoto, 比呂志 坂本, Setsuo Arikawa, 節夫 有川 · QIR (Kyushu University Institutional Repository) (Kyushu University) · 2001
In this paper, we consider a data mining problem for semi-structured data. Modeling semi-structured data as labeled ordered trees, we present an efficient algorithm for discovering frequent substructures from a large collection of semi-structured data. By extending the enumeration technique developed by Bayardo (SIGMOD'98) for discovering long itemsets, our algorithm scales almost linearly in the total size of maximal tree patterns contained in an input collection depending mildly on the size of the longest pattern. We also developed several pruning techniques that significantly speed-up the search. Experiments on Web data show that the our algorithm runs efficiently on real-life datasets combined with proposed pruning techniques in the wide range of parameters.