Mining Rooted Ordered Trees under Homeomorphism.
Mostafa Haghir Chehreghani, Maurice Bruynooghe · arXiv (Cornell University) · 2014
Mining frequent tree patterns has many practical applications in different areas such as XML data, bioinformatics and World Wide Web. The crucial step in frequent pattern mining is frequency counting which involves performing a matching operator to find occurrences (instances) of a pattern tree in database trees. A widely used matching operator for tree-structured data is subtree homeomorphism, where an edge in the pattern tree is mapped onto an ancestor-descendant relationship in the database tree. Tree patterns that are frequent under subtree homeomorphism are usually called embedded patterns. In this paper, we present an efficient algorithm for subtree homeomorphism with application to frequent pattern mining. We propose a compact data-structure, called occ, which can encode and represent several occurrences of a pattern tree. We then define efficient join operations on the occ data-structure, which help us count occurrences of tree patterns according to occurrences of their proper subtrees. Based on the proposed subtree homeomorphism method, we develop an effective pattern mining algorithm, called TPMiner. We evaluate the efficiency of TPMiner on several real-world and synthetic datasets. Our extensive experiments confirm that TPMiner always outperforms well-known existing algorithms, and in several cases the improvement with respect to a specific existing algorithm is significant.