Efficient frequent pattern mining based on Linear Prefix tree

摘要

Outstanding frequent pattern mining guarantees both fast runtime and low memory usage with respect to various data with different types and sizes. However, it is hard to improve the two elements since runtime is inversely proportional to memory usage in general. Researchers have made efforts to overcome the problem and have proposed mining methods which can improve both through various approaches. Many of state-of-the-art mining algorithms use tree structures, and they create nodes independently and connect them as pointers when constructing their own trees. Accordingly, the methods have pointers for each node in the trees, which is an inefficient way since they should manage and maintain numerous pointers. In this paper, we propose a novel tree structure to solve the limitation. Our new structure, LP-tree (Linear Prefix - Tree) is composed of array forms and minimizes pointers between nodes. In addition, LP-tree uses minimum information required in mining process and linearly accesses corresponding nodes. We also suggest an algorithm applying LP-tree to the mining process. The algorithm is evaluated through various experiments, and the experimental results show that our approach outperforms previous algorithms in term of the runtime, memory, and scalability.