Mining frequent patterns by pattern-growth
ACM SIGKDD Explorations NewsletterPublished 1 December 2000Open access
Jiawei Han, Jian Pei
Citations275
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that frequent pattern growth is efficient at mining large databases and its further development may lead to scalable mining of many other kinds of patterns as well.
Abstract
Mining frequent patterns has been a focused topic in data mining research in recent years, with the developmeht of numerous interesting algorithms for mining association, correlation, causality, sequential patterns, partial periodicity, constraint-based frequent pattern mining, associative classification, emerging patterns, etc. Most of the previous studies adopt an Apriori-like, candidate generation-and-test approach. However, based on our analysis, candidate generation and test may still be expensive, especially when encountering long and numerous patterns. A new methodology, called f r e q u e n t p a t t e r n growth, which mines frequent patterns without candidate generation, has been developed. The method adopts a divide-andconquer philosophy to project and partition databases based on the currently discovered frequent patterns and grow such patterns to longer ones in the projected databases. Moreover, efficient data structures have been developed for effective database compression and fast in-memory traversal. Such a methodology may eliminate or substantially reduce the number of candidate sets to be generated and also reduce the size of the database to be iteratively examined, and, therefore, lead to high performance. In this paper, we provide an overview of this approach and examine its methodology and implications for mining several kinds of frequent patterns, including association, frequent closed itemsets, max-patterns, sequential patterns, and constraint-based mining of frequent patterns. We show that frequent pattern growth is efficient at mining large databases and its further development may lead to scalable mining of many other kinds of patterns as well.
Keywords
Computer Science
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
ACM SIGMOD RecordMining frequent patterns without candidate generation
6,360 Citations2000Jiawei Han, Jian Pei +1 more
Mining sequential patterns
5,115 Citations2002R. K. Agrawal, Ramakrishnan Srikant
Three algorithms are presented to solve the problem of mining sequential patterns over databases of customer transactions, and empirically evaluating their performance using synthetic data shows that two of them have comparable performance.
Mining frequent patterns without candidate generation
3,195 Citations2000Jiawei Han, Jian Pei +1 more
This study proposes a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develops an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth.
Lecture notes in computer scienceMining sequential patterns: Generalizations and performance improvements
2,686 Citations1996Ramakrishnan Srikant, Rakesh Agrawal
This work adds time constraints that specify a minimum and/or maximum time period between adjacent elements in a pattern, and relax the restriction that the items in an element of a sequential pattern must come from the same transaction.
Integrating classification and association rule mining
2,223 Citations1998Bing Liu, Wynne Hsu +1 more
The integration is done by focusing on mining a special subset of association rules, called class association rules (CARs), and shows that the classifier built this way is more accurate than that produced by the state-of-the-art classification system C4.5.
PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth
1,791 Citations2005Jian Pei, Jiawei Han +5 more
This work proposes a novel sequential pattern mining method, called Prefixspan (i.e., Prefix-projected - Ettern_ mining), which explores prejxprojection in sequential pattern Mining, and shows that Pre fixspan outperforms both the Apriori-based GSP algorithm and another recently proposed method; Frees pan, in mining large sequence data bases.
Data Mining and Knowledge DiscoveryDiscovery of Frequent Episodes in Event Sequences
1,445 Citations1997Heikki Mannila, Hannu Toivonen +1 more
This work gives efficient algorithms for the discovery of all frequent episodes from a given class of episodes, and presents detailed experimental results that are in use in telecommunication alarm management.
Efficiently mining long patterns from databases
1,297 Citations1998Roberto J. Bayardo
A pattern-mining algorithm that scales roughly linearly in the number of maximal patterns embedded in a database irrespective of the length of the longest pattern, compared with previous algorithms that scale exponentially with longest pattern length.
Beyond market baskets
1,287 Citations1997Sergey Brin, Rajeev Motwani +1 more
This work develops the notion of mining rules that identify correlations (generalizing associations), and proposes measuring significance of associations via the chi-squared test for correlation from classical statistics, enabling the mining problem to reduce to the search for a border between correlated and uncorrelated itemsets in the lattice.
Efficient mining of emerging patterns
1,005 Citations1999Guozhu Dong, Jinyan Li
It is believed that EPs with low to medium support, such as 1%-20%, can give useful new insights and guidance to experts, in even “well understood” applications.
CLOSET : An Efficient Algorithm for Mining Frequent Closed Itemsets
829 Citations2000Jian Pei
FreeSpan
803 Citations2000Jiawei Han, Jian Pei +4 more
Permission to make digital or hard copies of part or all of this work or personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear the full citation on the first page.
Mining association rules with item constraints
769 Citations1997Ramakrishnan Srikant, Quoc Vu +1 more
This work considers the problem of integrating constraints that are Boolean expressions over the presence or absence of items into the association discovery algorithm and presents three integrated algorithms for mining association rules with item constraints and discusses their tradeoffs.
Exploratory mining and pruning optimizations of constrained associations rules
713 Citations1998Raymond T. Ng, Laks V. S. Lakshmanan +2 more
An architecture that opens up the black-box, and supports constraint-based, human-centered exploratory mining of associations, and introduces and analyzes two properties of constraints that are critical to pruning: anti-monotonicity and succinctness.
Knowledge Discovery and Data MiningEfficient algorithms for discovering association rules
630 Citations1994Heikki Mannila, Hannu Toivonen +1 more
An improved algorithm for the problem of mining association rules from large collections of data based on careful combinatorial analysis of the information obtained in previous passes is given, which makes it possible to eliminate unnecessary candidate rules.
Efficient mining of partial periodic patterns in time series database
581 Citations1999Jiawei Han, Guozhu Dong +1 more
This work presents several algorithms for efficient mining of partial periodic patterns by exploring some interesting properties related to partial periodicity such as the Apriori property and the max-subpattern hit set property, and by shared mining of multiple periods.
Journal of Parallel and Distributed ComputingA Tree Projection Algorithm for Generation of Frequent Item Sets
506 Citations2001Ramesh C. Agarwal, Charų C. Aggarwal +1 more
This paper provides an implementation of the tree projection method which is up to one order of magnitude faster than other recent techniques in the literature and has a well-structured data access pattern which provides data locality and reuse of data for multiple levels of the cache.
ACM SIGMOD RecordBottom-up computation of sparse and Iceberg CUBE
464 Citations1999Kevin Beyer, Raghu Ramakrishnan
SPIRIT: Sequential Pattern Mining with Regular Expression Constraints
451 Citations1999Minos Garofalakis, Rajeev Rastogi +1 more
A family of novel algorithms for mining frequent sequential patterns that also satisfy user-specified RE constraints that provide valuable insights into the tradeoffs that arise when constraints that do not subscribe to nice properties are integrated into the mining process.
Cyclic association rules
404 Citations2002B. Ozden, Sridhar Ramaswamy +1 more
This work devise a new technique called cycle pruning, which reduces the amount of time needed to find cyclic association rules by studying the interaction between association rules and time, and presents two new algorithms for discovering such rules.
Constraint-based rule mining in large, dense databases
359 Citations1999Roberto J. Bayardo, R. K. Agrawal +1 more
Computing Iceberg Queries Efficiently
341 Citations1998Min Fang, Narayanan Shivakumar +3 more
This work proposes efficient algorithms to evaluate iceberg queries using very little memory and significantly fewer passes over data, as compared to current techniques that use sorting or hashing.
Mining frequent itemsets with convertible constraints
324 Citations2002Jian Pei, Jiawei Han +1 more
A notion of convertible constraints is developed and systematically analyzed, classify, and characterize this class and techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining are developed.
Bottom-up computation of sparse and Iceberg CUBE
238 Citations1999Kevin Beyer, Raghu Ramakrishnan
The pruning in BUC, combined with an efficient sort method, enables BUC to outperform all previous algorithms for sparse CUBEs, even for computing entire CUBes, and to dramatically improve Iceberg-CUBE computation.
Can we push more constraints into frequent pattern mining?
191 Citations2000Jian Pei, Jiawei Han
Permission to make digital or hard copies of part or all of this work or personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear the full citation on the first page.
Efficient mining of constrained correlated sets
160 Citations2002Gösta Grahne, Laks V. S. Lakshmanan +1 more
It turns out that constraints can have subtle interactions with correlated item sets, depending on their underlying properties, and this work delineates the meaning of these two spaces and gives algorithms for computing them.
ACM SIGMOD RecordOptimization of constrained frequent set queries with 2-variable constraints
157 Citations1999Laks V. S. Lakshmanan, Raymond T. Ng +2 more
Scalable Techniques for Mining Causal Structures
112 Citations1998Craig Silverstein, Sergey Brin +2 more
Optimization of constrained frequent set queries with 2-variable constraints
82 Citations1999Laks V. S. Lakshmanan, Raymond T. Ng +2 more
A notion of quasi-succinctness is introduced, which allows a quasi-Succinct 2-var constraint to be reduced to two succinct 1-var constraints for pruning, and a query optimizer is proposed that is ccc-optimal, i.e., minimizing the effort incurred w.r.t. constraint checking and support counting.
FigshareRatio Rules: A New Paradigm for Fast, Quantifiable Data Mining
52 Citations2018Flip Korn, Alexandros Labrinidis +2 more