Mining Maximally Common Substructures from XML Trees with Lists-Based Pattern-Growth Method

With the continuous growth in XML data sources over the Internet, the discovery of useful information from a col- lection of XML documents is currently one of the main re- search areas occupying the data mining community. The mostly used approach to this task is to extract frequently oc- curred subtrees in XML trees. But, because the number of frequent subtrees grows exponentially with the size of trees, a more practical and scalable alternative is required, which is the discovery of maximal frequent subtrees. In this paper, we present the first algorithm that directly discovers maxi- mal frequent subtrees from a concise data structure, without any candidate subtree generation.