From path tree to frequent patterns: a framework for mining frequent patterns

We propose a framework for mining frequent patterns from large transactional databases. The core of the framework is a coded prefix-path tree with two representations, namely, a memory-based prefix-path tree and a disk-based prefix-path tree. The disk-based prefix-path tree is simple in its data structure yet rich in information contained, and is small in size. The memory-based prefix-path tree is simple and compact. Based on the memory-based prefix-path tree, a new depth-first frequent pattern discovery algorithm, called PP-Mine, is proposed that outperforms FP-growth significantly. The memory-based prefix-path tree can be stored on disk using a disk-based prefix-path tree with assistance of the new coding scheme. We present loading algorithms to load the minimal required disk-based prefix-path tree into main memory. Our technique is to push constraints into the loading process, which has not been well studied yet.