A Partition-Based Approach for Sequential Patterns Mining

Sequential patterns mining has been explored for various data types, and its computational complexity is well understood. There are well-known methods to deal effectively with computational problems such as GSP [1] and PrefixSpan [2]. However, most methods show limited performance due to the exponen...

Full description

Saved in:
Bibliographic Details
Main Authors: Nguyen, S.N., Orlowska, M.E.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm
Australia
Computational complexity
Data mining
Fault detection
Fault diagnosis
Itemsets
Partitioning algorithms
Pattern analysis
Pattern matching
Sequential Patterns
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Sequential patterns mining has been explored for various data types, and its computational complexity is well understood. There are well-known methods to deal effectively with computational problems such as GSP [1] and PrefixSpan [2]. However, most methods show limited performance due to the exponential number of growing patterns. Moreover when the input data set is very large, it is unsolvable because of main memory limitation. This paper shows a partition-based approach to overcome this drawback, and to provide further performance enhancements of sequential patterns computation. Furthermore, the partition-based approach can be extended to the parallel paradigm of mining sequential patterns. We have made a series of observations that has led us to invent data pre-processing methods such that the final step of the partition-based algorithm, where a combination of all local candidate patterns must be processed, is executed on substantially smaller input data. This paper shows results from several experiments that confirmed our general and formally presented observations.
DOI:10.1109/RIVF.2007.369157