A Fast Algorithm for Mining Frequent Ordered Subtrees

摘要

In this research, the authors took up the problem of discovering frequent ordered subtree patterns in tree structured data sets, which is of note in the actively researched area of frequent partial structure mining for semistructured data. With conventional algorithms, nonredundant frequent candidate tree enumeration is performed using rightmost expansion, but a problem with that approach is the enumeration of a large number of infrequent candidate trees. Accordingly, the authors propose a right-and-left tree join in order for the efficient enumeration of frequent candidate trees, from small-sized frequent trees to larger frequent candidate trees. Furthermore, the authors constructed AMIOT as an algorithm for discovering frequent ordered subtree patterns using the right-and-left tree join for candidate tree enumeration. A performance evaluation using artificial data and XML data indicated that AMIOT was 2.5 to 5 times faster than existing algorithms.