A Parallel Algorithm for Graph Transaction Based Frequent Subgraph Mining

摘要

Frequent subgraph patterns play an important role in feature mining for graph data. The problem of mining these patterns is defined as finding subgraphs that appear frequently according to a given frequency threshold. Usually, frequent subgraph mining (FSM) is conducted in graph transaction setting, in which graph database contains many small graphs. Since multicore processors are quite popular this day, many algorithms can be accelerated with multi-thread technique. This paper proposed a multi-thread frequent subgraph mining algorithm and achieved considerable acceleration in the experiments. In this paper, a parallel frequent subgraph mining algorithm named PTRGRAM (Parallel Transaction based Graph Mining) which can take full advantage of the multi-core performance of current processors was proposed. In the algorithm, the data synchronization between multiple threads is based on the producer-consumer model. In addition, to speed the support computing, the embedding node list is introduced for optimization. Finally, experimental performance evaluations were conducted with two graph datasets, demonstrating that the proposed algorithm outperforms the single-threaded gSpan and FFSM algorithm.