Fast Frequent Free Tree Mining in Graph Databases

Free tree, as a special graph which is connected, undirected and acyclic, is extensively used in domains such as computational biology, pattern recognition, computer networks, XML databases, etc. In this paper, we present a computationally efficient algorithm F3TM (fast frequent free tree mining) to discover all frequent free trees in a graph database. We focus ourselves on how to reduce the cost of candidate generation and minimize the number of candidates being generated. We prove a theorem that the completeness of frequent free trees can be guaranteed by growing vertices from a limited range of vertices in a free tree. Two pruning techniques, automorphism-based pruning and pruning based on canonical mapping are proposed which significantly reduce the cost of candidate generation. We conducted experimental studies on a real application dataset and we show that our F3TM outperforms the up-to-date algorithms by an order of magnitude