Mining High Utility Itemsets Using Prefix Trees and Utility Vectors
- 13 March 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 35 (10) , 10224-10236
Abstract
High utility itemsets can reveal combinations of items that have a high profit, expense, or importance. Mining high utility itemsets in a database with $n$ items generally results in a huge search space, composed of $2^{n}$ itemsets, and heavy utility calculations for the explored itemsets. Previous algorithms using prefix tree structures perform two phases, namely candidate generation and testing. To avoid generating candidate itemsets, one-phase algorithms use list or hyper-link structures and have been proven to be superior to two-phase algorithms. However, it should be noted that a prefix tree is still an efficient structure for itemset mining problems, and especially algorithms using prefix trees such as FP-Growth have shown excellent performance for mining frequent itemsets. This paper proposes Hamm, a High-performance AlgorithM for Mining high utility itemsets. Hamm employs a novel TV (prefix Tree and utility Vector) structure and mines high utility itemsets in one phase without candidate generation. We also develop an efficient optimization which is incorporated into Hamm as a component. Using prefix trees and utility vectors, Hamm outperforms state-of-the-art algorithms on various databases in experiments. Experimental results also show that the proposed optimization remarkably reduces the search space and speeds up Hamm.Keywords
Funding Information
- Key Agricultural Programs of Science and Technology and Innovation of Xiangyang (2020ABA002240)
- National Natural Science Foundation of China (61672389)
- Guangzhou Key Laboratory of Big Data and Intelligent Education (201905010009)
- Science and Technology Development Program of Central Guide to Local Government of China (2019ZYYD043)
This publication has 50 references indexed in Scilit:
- Mining High Utility Patterns in One Phase without Generating CandidatesIEEE Transactions on Knowledge and Data Engineering, 2015
- Mining High Utility Itemsets in Big DataLecture Notes in Computer Science, 2015
- Pruning strategies for mining high utility itemsetsExpert Systems with Applications, 2015
- Mining high utility itemsets by dynamically pruning the tree structureApplied Intelligence, 2013
- Direct Discovery of High Utility Itemsets without Candidate Generation2012
- BISCACM Transactions on Knowledge Discovery From Data, 2010
- Isolated items discarding strategy for discovering high utility itemsetsData & Knowledge Engineering, 2008
- BitTableFI: An efficient mining frequent itemsets algorithmKnowledge-Based Systems, 2007
- Mining itemset utilities from transaction databasesData & Knowledge Engineering, 2006
- Cache-conscious frequent pattern mining on modern and emerging processorsThe VLDB Journal, 2006