Is Single Scan based Restructuring Always a Suitable Approach to Handle Incremental Frequent Pattern Mining?

Abstract

Incremental mining of frequent patterns has attracted the attention of researchers in the last two decades. The researchers have explored the frequent pattern mining from incremental database problems by considering that the complete database to be processed can be accommodated in systems’ main memory even after the database gets updated very frequently. The FP-tree-based approaches were able to draw more interest because of their compact representation and requirement of a minimum number of database scans. The researchers have developed a few FP-tree based methods to handle the incremental scenario by adjusting or restructuring the tree prefix paths. Although the approaches have managed to solve the re-computation problem by constructing a complete pattern tree data structure using only one database scan, restructuring the prefix paths for each transaction is a computationally costly task, leading to the high tree construction time. If the FP-tree construction process can be supported with suitable data structures, reconstruction of the FP-tree from scratch may be less time consuming than the restructuring approaches in case of incremental scenario. In this study, we have proposed a tree data structure called Improved Frequent Pattern tree (Improved FP-tree). The proposed Improved FP-tree construction algorithm has immensely improved the performance of tree construction time by resourcefully using node links, maintained in header table to manage the same item node list in the FP-tree. The experimental results emphasize the significance of the proposed Improved FP-tree construction algorithm over a few conventional incremental FP-tree construction algorithms with prefix path restructuring.