An Efficient Algorithm for Mining Frequent Unordered Trees from Semi-structured Data

摘要

In this paper, we study a data raining 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 UNOT 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{sup}2m} per pattern, where k is the size of T, 6 is the branching factor of the data tree, and m is the total number of occurrences of T in the data trees.