OPHEP-Miner: One-phase high-efficiency pattern mining utilizing tree structures

High-efficiency pattern mining aims to identify patterns generating substantial utility while minimizing costs. The existing mining methods mainly employ the pattern combination strategy or projection technology to generate high-order patterns, thereby resulting in a large number of candidate patterns. Although the generation of invalid patterns can be avoided by storing the transaction dataset in a tree structure for mining, this approach is considered time-consuming. To address this issue, we employed the prefix tree and utility vector structure to discover high-efficiency patterns within one phase. To further enhance mining efficiency, a bottom-up single-path pattern enumeration method was designed, which eliminates the need for complex tree structure constructions. Additionally, three pruning strategies were devised to limit the pattern search space, including a novel pruning technique specifically designed for single-path scenarios. The effectiveness of the proposed algorithm has been validated through comparative analyses conducted on eight diverse datasets using five algorithms. The results show that the proposed algorithm outperforms other approaches, particularly due to its effective pruning techniques, which enable it to run up to 64 times faster than the best competing algorithm in some cases. Furthermore, we used a movie dataset as a case study to illustrate the applicability of our proposed approach.

Authors

• Xuan Liu Xinyang Normal University
• Genlang Chen
• Fangyu Wu
• Wanli Zuo
• Youxi Wu

Keywords

• High-utility pattern mining
• High-efficiency pattern
• Tree structure
• Pruning strategy