An efficient algorithm for mining closed itemsets.
This paper presents a new efficient algorithm for mining frequent closed itemsets. It enumerates the closed set of frequent itemsets by using a novel compound frequent itemset tree that facilitates fast growth and efficient pruning of search space. It also employs a hybrid approach that adapts search strategies, representations of projected transaction subsets, and projecting methods to the characteristics of the dataset. Efficient local pruning, global subsumption checking, and fast hashing methods are detailed in this paper. The principle that balances the overhead of search space growth and pruning is also discussed. Extensive experimental evaluations on real world and artificial datasets showed that our algorithm outperforms CHARM by a factor of five and is one to three orders of magnitude more efficient than CLOSET and MAFIA.
Liu
Jun-qiang
JQ
Institute of Artificial Intelligence, Zhejiang University; Hangzhou University of Commerce, Hangzhou 310035, China. liujunq@mail.hz.zj.cn
Pan
Yun-he
YH
D000465:Algorithms; D001185:Artificial Intelligence; D019295:Computational Biology / Q000379:methods*; D003628:Database Management Systems; D016208:Databases, Factual; D016247:Information Storage and Retrieval / Q000379:methods*