Mining Long Patterns - Frequent Pattern Mining - page 101

of mining long patterns has remained a challenge due to the prohibitively large num-
ber of smaller patterns which often need to be generated first in traditional mining
frameworks. In this chapter, we first use a pattern lattice model to illustrate and
compare various mining paradigms. We group existing mining algorithms into three
categories based on the way they traverse the pattern lattice, which are pattern enu-
meration, pattern merging and pattern traversal. We present recent studies for mining
long patterns according to their respective pattern mining paradigms. For each cate-
gory, we discuss the representative algorithms and the state-of-the-art development.
These studies provide valuable insight into the problem of long pattern mining and
give inspiration for future works.
References
1. R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In VLDB , pages 487-
499, 1994.
2. R. Agrawal, C. C. Aggarwal, and V. V. V. Prasad. Depth first generation of long patterns. In
Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and
Data Mining (KDD-2000) , pages 108-118, 2000. Also available as IBM Research Report,
RC21538, 1999.
3. T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Satamoto, and S. Arikawa. Efficient substructure
discovery from large semi-structured data. In SDM , pages 158-174, 2002.
4. Roberto J. Bayardo. Efficiently mining long patterns from databases, pages 85-93, 1998.
5. C. Borgelt and M. Berthold. Mining molecular fragments: Finding relevant substructures of
molecules. In ICDM , pages 211-218, 2002.
6. D. Burdick, M. Calimlim, J. Flannick, J. Gehrke, and T.Yiu. Mafia: A maximal frequent itemset
algorithm. IEEE Transactions on Knowledge and Data Engineering , 17(11):1490-1504, 2005.
7. K. Gouda and M. Zaki. Genmax: An efficient algorithm for mining maximal frequent itemsets.
Data Min. Knowl. Discov. , 11(3):223-242, November 2005.
8. J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M.-C. Hsu. Freespan: Frequent pattern-
projected sequential pattern mining. In Proceedings of the Sixth ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining , KDD '00, pages 355-359, New York,
NY, USA, 2000. ACM.
9. J. Han, J. Pei, Y. Yin, and R. Mao. Mining frequent patterns without candidate generation: A
frequent-pattern tree approach. Data Min. Knowl. Discov. , 8(1):53-87, January 2004.
10. J. Huan, W. Wang, and J. Prins. Efficient mining of frequent subgraph in the presence of
isomorphism. In ICDM , pages 549-552, 2003.
11. A. Inokuchi, T. Washio, and H. Motoda. An apriori-based algorithm for mining frequent
substructures from graph data. In PKDD , pages 13-23, 2000.
12. R. Jin, C. Wang, D. Polshakov, S. Parthasarathy, and G. Agrawal. Discovering frequent topolog-
ical structures from graph datasets. In Proceedings of the Eleventh ACM SIGKDD International
Conference on Knowledge Discovery in Data Mining , KDD '05, pages 606-611, New York,
NY, USA, 2005. ACM.
13. M. Kuramochi and G. Karypis. Frequent subgraph discovery. In ICDM , pages 313-320, 2001.
14. S. Kurtz, JV. Choudhuri, E. Ohlebusch, C. Schleiermacher, J. Stoye, and R. Giegerich. Reputer:
the manifold applications of repeat analysis on a genomic scale. In Nucleic Acids Research ,
number 22, pages 4633-4642, 2001.
15. D. Lo, S-C. Khoo, and C. Liu. Efficient mining of iterative patterns for software specification
discovery. In KDD , pages 460-469, 2007.