Abstract
Since semi-structured data such as XML files are widely used for data representation and exchange through the Internet, discovering frequent tree patterns over semi-structured data streams becomes an interesting issue. In this thesis, we propose an online algorithm to continuously compute the current set of frequent tree patterns from the data stream. A novel technique is introduced to incrementally generate all candidate tree patterns without duplicates in an efficient way. Moreover, a framework for counting the approximate frequency of the candidate tree patterns is adopted. Combining these techniques, the proposed algorithm is capable of computing frequent tree patterns with guarantees on completeness and accuracy. The experiment results show that this algorithm is both efficient and scalable.