Mining frequent patterns without candidate generation
Jiawei Han, Jian Pei, Yiwen Yin
ACM SIGMOD Record · 2000 · 6,467 citations
No retraction on record in OpenAlex.Check Crossref now
Cite this paper
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12. https://doi.org/10.1145/335191.335372
In text: (Han et al., 2000)
Ask a question about this research
One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.
Abstract
Mining frequent patterns in transaction databases, time-series databases, and many other kinds of databases has been studied popularly in data mining research. Most of the previous studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate set generation is still costly, especially when there exist prolific patterns and/or long patterns. In this study, we propose a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develop an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth. Efficiency of mining is achieved with three techniques: (1) a large database is compressed into a highly condensed, much smaller data structure, which avoids costly, repeated database scans, (2) our FP-tree-based mining adopts a pattern fragment growth method to avoid the costly generation of a large number of candidate sets, and (3) a partitioning-based, divide-and-conquer method is used to decompose the mining task into a set of smaller tasks for mining confined patterns in conditional databases, which dramatically reduces the search space. Our performance study shows that the FP-growth method is efficient and scalable for mining both long and short frequent patterns, and is about an order of magnitude faster than the Apriori algorithm and also faster than some recently reported new frequent pattern mining methods.
Related papers
- A relational model of data for large shared data banks1970
- The entity-relationship model—toward a unified view of data1976
- A relational model of data for large shared data banks1983
- Mining association rules between sets of items in large databases1993
- An overview of data warehousing and OLAP technology1997
Metadata from OpenAlex (CC0). Citations are generated from the published record.