Efficient Mining of Frequent Itemsets Using Only One Dynamic Prefix Tree

IEEE Access

Zhao Wu¹  Jun-Feng Qu¹  Qiong Gu¹  Bo Hang¹  Zhongbo Wu¹  Bo Tang² 

[1] School of Computer Engineering, Hubei University of Arts and Science, Xiangyang, China;School of Mathematics and Statistics, Hubei University of Arts and Science, Xiangyang, China;

关键词: Frequent itemset;    post-conditional database;    dynamic prefix tree;   

DOI  :  10.1109/ACCESS.2020.3029302

来源: DOAJ

【 摘 要 】

Frequent itemset mining is a fundamental problem in data mining area because frequent itemsets have been extensively used in reasoning, classifying, clustering, and so on. To mine frequent itemsets, previous algorithms based on a prefix tree structure have to construct many prefix trees, which is very time-consuming. In this paper, we propose a novel frequent itemset mining algorithm called DPT (Dynamic Prefix Tree) which uses only one prefix tree. We first introduce the concept of the post-conditional database of an itemset, and analyze the distribution of an itemset's post-conditional database in a prefix tree representing a database. Subsequently, we illuminate how DPT adjusts the prefix tree to mine frequent itemsets and give three optimization techniques. An interesting advantage of DPT is that the algorithm can directly output a prefix tree representing all frequent itemsets after slight modifications. Using only one dynamic prefix tree, DPT avoids the high cost of constructing many prefix trees and thus gains significant performance improvement. Experimental results show that DPT remarkably outperforms previous algorithms with respect to running time and memory usage, and that a prefix tree representing all frequent itemsets DPT outputs can be used more efficient than a list representing them previous algorithms output.

【 授权许可】

Unknown