  High-utility itemset mining finds itemsets from a transaction database with
utility no less than a fixed user-defined threshold. The utility of an itemset
is defined as the sum of the utilities of its item. Several algorithms were
proposed to mine high-utility itemsets. However, no state-of-the-art algorithm
performs consistently good across dense and sparse datasets. In this paper, we
propose a novel data structure called Utility-Tree, and a tree-based algorithm
called UT-Miner that mines high-utility itemsets in one-phase only without
generating any candidates and uses a lightweight construction method to reduce
the cost of creating projected databases during the search space exploration.
The transaction information is stored compactly with every node of the
Utility-Tree, and the information is computed efficiently during the recursive
invocation of the algorithm. Experimental results on several real-life dense
and sparse datasets reveal that UT-Miner is among the top-performing efficient
algorithms across different datasets.
