Sequential Pattern Mining Algorithms: Trade-offs between Speed and Memory
See where this sits in the topic map →Summary AI-generated
- TL;DR
- As structured pattern mining sees broader application, understanding the trade-offs between speed and memory in existing algorithms becomes essential.
- Problem
- While pattern-growth methods generally outperform apriori-based methods in sequential pattern mining, the reasons behind their advantages have not been well understood.
- Method
- This paper provides a detailed performance and memory analysis of these algorithms, identifying support-counting as the most computationally demanding step and showing how projected databases restrict the search space.
- Results
- The analysis reveals that pattern-growth methods achieve superior performance by restricting the search space through projected databases.
- Contributions
- The paper presents a comprehensive analysis of sequential pattern mining algorithms and describes how apriori-based approaches can match the efficiency of pattern-growth methods.
- Limitations
- Not specified in the abstract.
- Takeaways
- Understanding the core mechanisms of pattern-growth methods allows apriori-based algorithms to be adapted for greater efficiency in sequential pattern mining.
- Applications
- Not specified in the abstract.
- Topics
- Sequential Pattern Mining Algorithms
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
Abstract. Increased application of structured pattern mining requires a perfect understanding of the problem and a clear identification of the advantages and disadvantages of existing algorithms. Among those algorithms, pattern-growth methods have been shown to have the best performance when applied to sequential pattern mining. However, their advantages over apriori-based methods are not well explained and understood. Detailed analysis of the performance and memory requirements for these algorithms shows that counting the support for each potential pattern is the most computationally demanding step. Additionally, the analysis makes clear that the main advantage of patterngrowth over apriori-based methods resides on the restriction of the search space that is obtained from the creation of projected databases. In this paper, we present this analysis and describe how apriori-based algorithms can achieve the efficiency of pattern-growth methods. 1