TL;DR
This paper introduces PPV, a novel vertical data mining algorithm that significantly speeds up frequent pattern discovery. By employing a compact "Node-list" data structure derived from a PPC-tree and an efficient intersection strategy, PPV outperforms existing methods like FP-growth and Eclat, especially on large and sparse datasets.
What Problem Does This Paper Address?
Mining frequent patterns is a cornerstone of data mining, essential for tasks like association rule discovery and sequential pattern analysis. Traditional methods fall into two main categories: Apriori-like (candidate generation and testing) and FP-growth (tree-based, no candidate generation). While vertical mining methods (like Eclat) offer advantages by representing items with transaction IDs (tid-lists), their performance degrades significantly with large transaction sets due to costly tid-list intersections. FP-growth, while efficient, can be memory-intensive and complex. This paper aims to bridge this gap by developing a vertical mining approach that is both memory-efficient and fast, overcoming the limitations of existing methods.
Methods
The core of the PPV algorithm lies in its novel data structure and intersection strategy:
- PPC-tree: A prefix-tree structure that stores transactions. Unlike FP-trees, PPC-trees include "Pre-Post codes" for each node, which are crucial for efficiently verifying ancestor-descendant relationships.
- Node-lists: For each frequent item, a Node-list is created. This list contains PP-codes of nodes in the PPC-tree that register the item. These lists are significantly more compact than traditional tid-lists or diffsets because transactions with common prefixes share nodes in the PPC-tree.
- Efficient Node-list Intersection: The algorithm generates candidate (k+1)-patterns by intersecting Node-lists of frequent k-patterns. This intersection is optimized to achieve an average time complexity of O(m+n), where m and n are the sizes of the Node-lists being intersected. This efficiency is achieved by leveraging the ordered nature of Node-lists and the Pre-Post codes to quickly determine ancestor-descendant relationships.
The overall PPV algorithm follows an Apriori-like structure, iteratively discovering frequent patterns of increasing length by intersecting the Node-lists of previously found frequent patterns.
Datasets
The paper evaluates PPV on a combination of synthetic and real-world datasets:
- Synthetic Datasets:
- T25.120.D100k (25 average transaction length, 100,000 transactions)
- T40.110.D100k (40 average transaction length, 100,000 transactions)
- T40.130.D1000k (40 average transaction length, 1,000,000 transactions) - This dataset was newly created for the study to test performance on large volumes of data.
- Real Dataset:
- Accidents (traffic accident records from Flanders, Belgium, 1991-2000)
Key Insights and Ideas
- Compactness of Node-lists: The paper highlights that Node-lists are substantially smaller than tid-lists or diffsets, especially on sparse datasets. This is a key factor in PPV's efficiency.
- Pre-Post Codes for Ancestor-Descendant Relationships: The use of Pre-Post codes in the PPC-tree provides a very efficient way to determine if one node is an ancestor of another, which is fundamental for the Node-list intersection process.
- Linear-Time Intersection: The proposed intersection algorithm for Node-lists achieves an average linear time complexity, a significant improvement over naive quadratic approaches.
- Synergy of Vertical and Tree-based Methods: PPV effectively combines the data compression benefits of tree-based structures (like FP-trees) with the efficient support counting of vertical mining methods.
Key Results
The experimental results demonstrate PPV's superiority over FP-growth, Eclat, and dEclat across various datasets and minimum support thresholds:
- Speedup: PPV consistently outperforms the other algorithms, often being twice as fast as FP-growth and dEclat on average.
- Scalability: PPV shows good scalability, particularly as the minimum support threshold decreases. While PPV and FP-growth exhibit similar scalability trends, PPV is generally faster.
- Performance on Sparse Data: The advantage of PPV is more pronounced on sparse datasets, where the Node-list compression is most effective.
- Node-list Size: Figures 9 and 10 show that Node-lists are significantly smaller (by one to two orders of magnitude) than tid-lists or diffsets for frequent patterns.
Limitations and Future Work
- Limitations: The paper acknowledges that while Node-list intersection is efficient, it is more complex than intersecting tid-lists or diffsets. This means the performance advantage of PPV over Eclat/dEclat is not as dramatic as the compression advantage of Node-lists.
- Future Work: The authors suggest extending PPV to mine specialized frequent patterns, such as closed frequent patterns, top-k frequent patterns, and sequential patterns, as interesting avenues for future research.
Summary updated