Incremental Mining of High Utility Patterns in One Phase by Absence and Legacy-Based Pruning

Abstract

Mining high utility patterns in dynamic databases is an important data mining task. While a naive approach is to mine a newly updated database in its entirety, the state-of-the-art mining algorithms all take an incremental approach. However, the existing incremental algorithms either take a two-phase paradigm that generates a large number of candidates that causes scalability issues or employ a vertical data structure that incurs a large number of join operations that leads to efficiency issues. To address the challenges with the existing incremental algorithms, this paper proposes a new algorithm incremental direct discovery of high utility patterns (Id2HUP+). Id2HUP+ adapts a one-phase paradigm by improving the relevance-based pruning and upper-bound-based pruning proposes a novel data structure for a quick update of dynamic databases and proposes the absence-based pruning and legacy-based pruning dedicated to incremental mining. The extensive experiments show that our algorithm is up to 1-3 orders of magnitude more efficient than the state-of-the-art algorithms, and is the most scalable algorithm.

Keywords

• Data mining
• utility mining
• high utility patterns
• pattern mining
• dynamic databases