negFIN: An efficient algorithm for fast mining frequent itemsets

摘要

Frequent itemset mining is a basic data mining task and has numerous applications in other data mining tasks. In recent years, some data structures based on sets of nodes in a prefix tree have been presented. These data structures store essential information about frequent itemsets. In this paper, we propose another efficient data structure, NegNodeset. Similar to other such data structures, the basis of NegNodeset is sets of nodes in a prefix tree. NegNodeset employs a novel encoding model for nodes in a prefix tree based on the bitmap representation of sets. Based on the NegNodeset data structure, we propose negFIN, which is an efficient algorithm for frequent itemset mining. The efficiency of the negFIN algorithm is confirmed by the following three reasons: (1) the NegNodesets of itemsets are extracted using bitwise operators, (2) the complexity of calculating NegNodesets and counting supports is reduced to O(n), where n is the cardinality of NegNodeset, and (3) it employs a set-enumeration tree to generate frequent itemsets and uses a promotion method to prune the search space in this tree. Our extensive performance study on a variety of benchmark datasets indicates that negFIN is the fastest algorithm, compared with previous state-of-the-art algorithms. However, our algorithm runs with the same speed as dFIN on some datasets. (C) 2018 Elsevier Ltd. All rights reserved.