Efficient High Utility Itemset Mining on Massive Data

In learning analytics and computer support for intelligent tutoring, high utility itemset mining (HUIM) is an interesting operation to find the sets of items which have high utilities. HUIM normally is considered to be more difficult than the traditional frequent itemset mining (FIM), since the utility of the itemset does not hold anti-monotone property. This paper analyzes the inefficiency of existing algorithms for HUIM on massive data. To address this, we introduce a novel algorithm named P2H, which utilizes a prefix-partitioning approach. P2H organizes the transaction table into memory-resident partitions. Each partition groups transactions that share a common initial item, enabling efficient discovery of high-utility itemsets. P2H handles the prefix-based partitions sequentially and independently. By the pre-computed data structure, P2H can skip most of the partitions and report the required high utility itemsets. For the partitions to be processed further, a set enumeration tree is proposed to compute the results quickly. Besides, a novel pruning strategy utilizing full suffix utilities is introduced to effectively reduce the exploration space. Extensive evaluation on both synthetic and real-world datasets demonstrates that P2H substantially outperforms state-of-the-art methods.