negFIN: An efficient algorithm for fast mining frequent itemsets

Nader Aryabarzan

doi:10.1016/j.eswa.2018.03.041

Return

negFIN: An efficient algorithm for fast mining frequent itemsets

2018-09-01

PRE

Nader Aryabarzan

Behrouz Minaei‐Bidgoli *

Mohammad Teshnehlab

DOI：10.1016/j.eswa.2018.03.041

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Prefix tree

Nodesets

Bitmap representation

Frequent itemsets

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.