Single Phase High Utility Pattern Mining for Dynamic Datasets

High utility mining is a new development of data mining technology. Previous solutions of this problem utilize a two-phase process with candidate generation approach that is inefficient and not scalable with large dynamic databases. Two-phase method suffers from scalability issue due to the huge number of candidates. This paper proposes a novel algorithm that finds high utility patterns in a single phase without generating candidates. The oddity lies in a high utility pattern growth approach, a lookahead strategy, and a linear data structure. Our pattern growth approach searches a reverse set enumeration tree and prune search space by utility upper bounding. It uses closure property and a singleton property to look ahead and identify high utility patterns without enumeration. A linear data structure enables us to compute a tight bound for powerful pruning and to directly identify high utility patterns in an efficient and scalable way, which targets the root cause with prior algorithms. Our algorithm can be 1 to 2 orders of magnitude more efficient and is more scalable than the traditional state-of-the-art algorithms.