Efficient top-k high utility itemset mining on massive data

In practical applications, top-k high utility itemset mining (top-k HUIM) is an interesting operation to find the k itemsets with the highest utilities. It is analyzed that, the existing algorithms only can deal with the small and medium-sized data, and their performance degrades significantly on massive data. This paper presents a novel top-k HUIM algorithm PTM which can mine top-k high utility itemsets on massive data efficiently. PTM maintains the transaction database as a set of prefix-based partitions, each of which can fit in the memory and keeps the transactions with the same prefix item. The utility of an itemset can be computed by the transactions in one particular partition. PTM processes the prefix-based partitions in the order of average transaction utility to raise utility threshold faster. By the concise assistant data structures, PTM can skip majority of the partitions directly. For the partitions to be processed, PTM utilizes depth-first search on the set enumeration tree of the promising items to find the required results. The full-suffix-utilitybased subtree pruning rule is devised to reduce the exploration space of set enumeration tree effectively. The extensive experimental results show that PTM can discover the top-k high utility itemsets on massive data efficiently. (C) 2020 Elsevier Inc. All rights reserved.