An efficient frequent pattern mining algorithm using a highly compressed prefix tree
Xiaolin Zhu, Yongguo Liu · Intelligent Data Analysis · 2019
The identification of frequent patterns plays a key role in mining association rules. FP-growth is a fundamental algorithm for frequent pattern mining. It employs a prefix tree structure (FP-Tree) and a recursive mining process to discover frequent patterns. However, the performance of FP-growth is closely related to the total number of recursive calls, which leads to poor performance when multiple conditional FP-trees are required to be constructed. This paper proposes highly compressed FP-tree (HCFP-tree). This increases prefix sharing and reduces the number of nodes in the prefix tree. Based on HCFP-tree, we design a new algorithm called HCFP-growth. This algorithm greatly reduces the number of recursive calls required to mine full frequent patterns. Experiments conducted on various types of datasets demonstrate that HCFP-growth is always among the fastest algorithms. It also consumes the least memory in many cases, and its memory consumption is comparable to that of existing algorithms in other cases.