A New Fast Vertical Method for Mining Frequent Patterns

Zhi-Hong Deng, Zhonghui WangInt. J. Comput. Intell. Syst 2010 · DOI

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

BibTeX
@article{deng2010new,
  author = {Zhi-Hong Deng and Zhonghui Wang},
  title = {{A New Fast Vertical Method for Mining Frequent Patterns}},
  journal = {Int. J. Comput. Intell. Syst.},
  year = {2010},
  doi = {10.1080/18756891.2010.9727736},
}
Figure