Document Type : Original Research Paper

Authors

• Mahnaz Naderi Vlashejerdi ¹
• Negin Daneshpour ²

¹ Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran

² Computer Engineering Department, Shahid Rajaee Teacher Training University, Tehran, Iran

Abstract

High utility itemset mining is a significant task within the data mining domain. Since real-world databases are dynamic and incremental, efficient methods are needed for mining high utility itemsets without repeatedly rescanning that database. This study proposes a new method for high utility itemset mining in dynamic and incremental databases.
The proposed method, referred to as HUIM-IncDa, employs a vertical list structure for mining high utility itemsets, which is constructed through a single scan of the database. Unlike approaches that require repeated database processing after updates, the proposed method incrementally maintains the vertical representation and associated utility information when new transactions arrive. Therefore, repeated database scans are not required when updates occur. The algorithm applies transaction-weighted utilization (twu) and subtree utility (su) for pruning the search space. The combination of incremental vertical-list maintenance and twu- and su-based pruning distinguishes the proposed approach by reducing both database access and the search space during high-utility itemset mining. In addition, discovered high utility itemsets are stored within a dedicated table to avoid redundant data storage.
The proposed algorithm was evaluated against five advanced high utility itemset mining algorithms on different benchmark datasets. The experimental results show substantial performance improvements in several settings. For example, in the scalability experiments, the proposed HUIM-IncDa algorithm reduced the average runtime by up to 78.2% compared with HUIMSU and by up to 47.0% compared with H-Miner across the evaluated datasets. It also reduced average memory consumption by up to 73.6% compared with HUIMSU and by up to 49.7% compared with H-Miner. The algorithm consistently outperformed or ranked among the best existing methods across different datasets and parameter settings.
The proposed method provides an efficient framework for identifying high utility itemsets in databases with dynamic and incremental updates. By eliminating repeated database scans and employing effective pruning strategies, it significantly improves computational efficiency. The obtained results indicate that the algorithm is a competitive and scalable approach for high utility itemset mining applications.

Keywords

• high utility itemset mining
• utility threshold
• pruning strategy
• dynamic database
• incremental database

Main Subjects

• Data Mining