CLOSET+: searching for the best strategies for mining frequent closed itemsets

By Jianyong Wang, Jiawei Han, Jian Pei. Knowledge Discovery and Data Mining, 2003

705 citations recorded by the source corpus.

Mining frequent closed itemsets provides complete and non-redundant results for frequent pattern analysis. Extensive studies have proposed various strategies for efficient frequent closed itemset mining, such as depth-first search vs. breadthfirst search, vertical formats vs. horizontal formats, tree-structure vs. other data structures, top-down vs. bottom-up traversal, pseudo projection vs. physical projection of conditional database, etc. It is the right time to ask "what are the pros and cons of the strategies?" and "what and how can we pick and integrate the best strategies to achieve higher performance in general cases?"In this study, we answer the above questions by a systematic study of the search strategies and develop a winning algorithm CLOSET+. CLOSET+ integrates the advantages of the previously proposed effective strategies as well as some ones newly developed here. A thorough performance study on synthetic and real data sets has shown the advantages of the strategies and the improvement of CLOSET+ over existing mining algorithms, including CLOSET, CHARM and OP, in terms of runtime, memory usage and scalability.

Subfields: Computational Theory and Mathematics, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e20e2e3d81d6a3c2ad8904774d2646a31dd77c92

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Jiawei Han
2. Hong Cheng
3. Xifeng Yan
4. Jianyong Wang
5. Gösta Grahne
6. Jianfei Zhu
7. Ching-Jui Hsiao
8. Dong Xin

In Information Systems

1. Jiawei Han
2. Hong Cheng
3. Xifeng Yan
4. Philip S. Yu
5. Dong Xin
6. Jianyong Wang
7. Mohammed J. Zaki
8. Yu Zheng

In Signal Processing

1. Yu Zheng
2. Jiawei Han
3. Xifeng Yan
4. Hong Cheng
5. Xing Xie
6. Philip S. Yu
7. Jianyong Wang
8. Dong Xin

Citations in the corpus

• Mining Individual Life Pattern Based on Location History (2009, methodology): “For non-sequential life patterns, we apply the closet+ [10] frequent pattern mining algorithm.”
• Swarm (2010, background): “In previous studies [19, 25, 21] on closed frequent pattern mining, there are three pruning rules (i.”
• Detection of Frequent Alarm Patterns in Industrial Alarm Floods Using Itemset Mining Methods (2018, background): “Frequent closed patterns can be discovered through 1) maintaining discovered patterns in a pattern tree, e.g., CLOSET+ [33]; and 2) tracking the TID list of a pattern, e.g., Closed Association Rule Mining (CHARM, “H” is gratuitous) [34].”
• Summarizing Significant Changes in Network Traffic Using Contrast Pattern Mining (2017, background): “An itemset X is closed [10] in a dataset D if it is frequent and there is no superset Y of X satisfying count(Y,D) = count(X,D).”
• Efficient algorithms for mining closed itemsets and their lattice structure (2005, methodology): “All of the current closed set mining algorithms such as Close [16], Pascal [3], Closet [17], Closet+ [20], Mafia [6], as well as CHARM, do not output the lattice explicitly.”
• Interactive and Deterministic Data Cleaning (2016, result): “The major difference of our lattice, in contrast to traditional closed item set lattice used for data mining [42], is that our lattice is dynamically changed.”
• Moment: maintaining closed frequent itemsets over a stream sliding window (2004, background): “, [16], [17]), only closedfrequent itemsets are discovered.”
• Fast algorithms for frequent itemset mining using FP-trees (2005, background): “Since all information contained in the database is compressed into the bitvectors, mining frequent itemsets and candidate frequent itemset generation can be done by bitvector and-operations.”
• BIDE: efficient mining of frequent closed sequences (2004, methodology): “In recent years many studies have presented convincing arguments that for mining frequent patterns (for both itemsets and sequences), one should not mine all frequent patterns but the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency [15”
• Frequent pattern mining: current status and future directions (2007, methodology): “(Wang et al. 2003) defined a preference model which captures the notion of unexpectedness.”