Constraint-based sequential pattern mining: the pattern-growth methods
Journal of Intelligent Information SystemsPublished 19 January 2007
Jian Pei, Jiawei Han, Wei Wang
Citations233
SJR quartileQ2
SJR score0.86
SNIP1.67
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
This study shows that constraints can be effectively and efficiently pushed deep into the sequential pattern mining under this new framework and can be extended to constraint-based structured pattern mining as well.
Abstract
Constraints are essential for many sequential pattern mining applications. However, there is no systematic study on constraint-based sequential pattern mining. In this paper, we investigate this issue and point out that the framework developed for constrained frequent-pattern mining does not fit our mission well. An extended framework is developed based on a sequential pattern growth methodology. Our study shows that constraints can be effectively and efficiently pushed deep into the sequential pattern mining under this new framework. Moreover, this framework can be extended to constraint-based structured pattern mining 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.
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
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.
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.
Machine LearningSPADE: An Efficient Algorithm for Mining Frequent Sequences
1,802 Citations2001Mohammed J. Zaki
SPADE is a new algorithm for fast discovery of Sequential Patterns that utilizes combinatorial properties to decompose the original problem into smaller sub-problems, that can be independently solved in main-memory using efficient lattice search techniques, and using simple join operations.
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.
Sequential PAttern mining using a bitmap representation
1,069 Citations2002Jay Ayres, Jason Flannick +2 more
A novel depth- first search strategy that integrates a depth-first traversal of the search space with effective pruning mechanisms is introduced that combines a vertical bitmap representation of the database with efficient support counting.
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.
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.
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.
Constraint-based rule mining in large, dense databases
359 Citations1999Roberto J. Bayardo, R. K. Agrawal +1 more
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.
Mining sequential patterns with constraints in large databases
240 Citations2002Jian Pei, Jiawei Han +1 more
This paper investigates the issue and shows that constraints can be effectively and efficiently pushed deep into sequential pattern mining under a new framework developed based on a sequential pattern growth methodology.
Efficient enumeration of frequent sequences
203 Citations1998Mohammed J. Zaki
SPADE utilizes combinatorial properties to decompose the original problem into smaller sub-problems, that can be independently solved in main-memory using efficient lattice search techniques, and using simple join operations.
Multi-dimensional sequential pattern mining
198 Citations2001Helen Pinto, Jiawei Han +4 more
This paper examines feasible combinations of efficient sequential pattern mining and multi-dimensional analysis methods, as well as develop uniform methods for high-performance mining, which integrates the multidimensional analysis and sequential data mining.
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.
Mining long sequential patterns in a noisy environment
156 Citations2002Jiong Yang, Wei Wang +2 more
The concept of compatibility matrix is introduced as the means to provide a probabilistic connection from the observation to the underlying true value and a new metric match is proposed to capture the "real support" of a pattern which would be expected if a noise-free environment is assumed.
TSP: mining top-K closed sequential patterns
112 Citations2004P. Tzvetkov, Xifeng Yan +1 more
ApproxMAP: Approximate Mining of Consensus Sequential Patterns
99 Citations2003Hye‐Chung Kum, Jian Pei +2 more
This paper presents an efficient and effective algorithm, ApproxMAP, to mine consensus patterns from large sequence databases in two steps, where sequences are clustered by similarity and consensus patterns are mined directly from each cluster through multiple alignment.
An efficient algorithm for mining frequent sequences by a new strategy without support counting
78 Citations2004Ding-Ying Chiu, Yi‐Hung Wu +1 more
This work proposes a new strategy called direct sequence comparison (abbreviated as DISC), which can find frequent sequences without having to compute the support counts of nonfrequent sequences and design an efficient algorithm called DISC-all to take advantages of all the four strategies.
How to quickly find a witness
29 Citations2003Daniel Kifer, Johannes Gehrke +2 more
This paper presents a more unified view of mining constrained itemsets such that most existing algorithms can be easily extended to handle constraints for which they were not designed a-priori.