Abstract
Tree structures are commonly adopted in many applications, such as bioinformatics, XML database, and web log databases. Mining frequent tree patterns can be valuable for query optimization, pattern classification, and web recommendation. However, one of the challenges for mining frequent subtrees is that the number of the candidate subtrees may exponentially grow with the tree size. In order to deal with such massive information, the closed subtrees is one of the promising solutions. In this paper, we propose an approach, named CSTMer (Closed Stream Tree Miner), for mining frequent subtrees over data streams by discovering the closed subtrees first. In the approach, we mainly introduce a compact structure, named closed global prefix tree, which maintains the associated information needed for deriving the closed subtrees. The size of the set of closed subtrees is usually smaller than the size of the set of all frequent subtrees. Therefore, the memory consumption needed for mining frequent subtrees can be reduced. In addition, we compare the proposed approach with STMer which discovers all frequent subtrees. The experiment result shows that our approach greatly reduces the memory consumption.